Using Visual Studio 2005 to migrate web parts today, I hit a strange problem. I got this error message after making only SLIGHT changes to my web part based on the SharePoint->Web Part project. It occurs when you make mysterious changes to your project, then try to Deploy it (right-click Project -> Deploy).
After a little experimentation, I determined it has something to do with the "Solution Name" under right-click Project -> Properties -> SharePoint Solution, and the name attribute of the tag of the solution.xml file. When I made changes only to the "Solution Name" in the Properties tab, and later to the solution.xml file in an attempt to fix it. I've even seen the "Solution Name" in the Properties NOT save over and over again as I tried to remove the dots (.), hyphen (-), and underscore (_) that I had in the value.
I was able to solve my problem by exiting Visual Studio, editing the solution.xml file and setting the name in the tag to exactly what I wanted (punctuation and all, for example name=“AAron.Whatever2.WebPart-1_0“). Then when I opened the solution, and looked at the project's “Solution Name“ under Properties, they were the same. Ahha, that's where the value REALLY REALLY comes from. Now my project deploys properly.
NOTE: I just had the problem again an hour later. I exited VS, opened the solution.xml file, saved the file, and reopened the solution and could build it, then I chose deploy, and it worked. This may be a red herring, but it did work.