The solution cannot be deployed. The feature 'some-feature-id' uses the directory "some-directory" in the solution

I recently came across this error when trying to deploy a WSP:
The solution cannot be deployed.  The feature 'some-feature-id' uses the directory "some-directory" in the solution. However, it is currently installed in the farm to the directory "some-other-directory". Uninstall the existing feature before you install a new version of the solution.

Simple enough, I tried to do an Uninstall-SPFeature as well as Uninstall-SPFeature -Force both of which did not help. Finally someone tried stsadm -o uninstallfeature and then the subsequent WSP deploy worked. I guess Powershell and stsadm are not quite equivalent