"Cannot uninstall Language Pack 0 because it is not deployed" when attempting to uninstall-spsolution on sharepoint 2010 foundation

I'm also seeing this error in one of our farms when I run the Update-SPSolution commandlet. Recently, we updated the farm with foundation and server Service Pack 1, the associated server language packs and the June Cumulative update. By chance, is this the patch level of your farm? Interestingly, I have no trouble running Update-SPSolution in another farm patched to the same level. The bottom-line is that I don't think this is limited to Uninstall-SPSolution or Update-SPSolution.

I just resolved the issue by doing the following:

1. Checked the solution store and saw that the solution I was updating was not deployed
2. I attempted to deploy the solution and saw that it was stuck in the deployment stage
3. From services.msc I stopped and restarted the SharePoint 2010 Timer service and the SharePoint 2010 Administration service. I don't normally stop and start SharePoint services from Services, but that seemed to do the trick. I also don't know whether it's necessary to recycle both of these services.
4. I then returned to the command line and was able to successfully update the solution.

Please let me know if this works for you.

While I like the answer above and I think it would work some of the time, in my case I had to remove the Errored out WSP from the solution store and then re-add it and then install/deploy it again. After that my updates were working fine again.

I had the same issue, I opened the manage solutions in central admin and there was an error message next to my solution. The error message was actually helpful, it directed me to solve the issue. I have added -force while installing the solution using power shell command then it worked fine. After that I deactivated and reactivated the feature just in case.