I removed a WSP from the solution store and tried to redeploy my code through Visual Studio 2008. I encountered the following error:
The language-neutral solution package was not found.
I am not sure of the cause - but I do know how to fix it: Close Visual Studio and reopen it.
Old school, but effective.