I stumbled upon this post from Mikhail Dikov who explains 7 reasons why a webpart may show up in the webpart chooser but give the mentioned error when adding it to a page.
None of his steps worked for me, but in the comments, Ian Campbell noted very helpfully to check the WebPart Gallery at site collection level. The gallery contained an old version (when looking at the XML) of the webpart, which still referenced a faulty assembly. I deleted it and re-enabled my feature (thus adding it again) and everything worked fine.
Good luck continuing to figure out if this didn’t work for you!