Quick tip for Visual Studio SharePoint developers. When you remove a web part from your project and you try to deploy it again you will get this error. To solve it, simply edit the manifest.xml file in the \pkg folder in your project folder and remove the reference to the item that has been removed:
Remove the item from the manifest.xml and save.
Now the project should deploy as it should.