If you develop, release and add a SharePoint 2010 sandboxed solution web part to a page, then change the web part type to non-sandboxed you may see the error: ” Web Part Error: The request could not be completed because the specified solution was not found”.

Just edit the page, delete the web part, then re-add the web part to the page.  This fixes the error.