I came across this error when trying to deploy a sandboxed solution. The first step in the process is to retract the solution currently in the store, it there is one. That’s fine, but this caused an error. It took me some time to figure out what was happening, so perhaps this post will help you spend less time on it 🙂
The solution was quite simple. My solution contains a feature which is deployed on web level. I altered a web template to staple the feature to this template so it is activated upon creation of a new site based on this template. I tested it by creating a site and deleted that site afterwards. But although the site (SPWeb actually) is deleted, it still lives in the recycle bin. And because the web is dependant on the template, and the template is dependant on my feature; I could not retract the solution with my feature in it.
Solved it by permanently deleting the site from the recycle bin. In online cases you should be able to just overwrite the WSP in the store with a new one without causing problems; but Visual Studio doesn’t support the Upgrade action for sandboxed solutions.