Today I tried to add a custom web part to a SharePoint 2010 web page. Web part was listed in while via Insert > Web Part gallery but SharePoint failed to add it to a web part page with the following error:
“The operation could not be completed because the item was removed from the gallery”
So if you are facing similar issues check your Visual Studio package and make sure this web part is being properly deployed. In my case it was somehow left out of default feature package. I just reinserted it back to the packaged and added web part back to page.
Hope this helps!