I get this message when trying to update or download some apps from the market. I say some because some work just fine. I have 7gb of free space. I tried to download a app that was less than 1mb and got this message then I tried to download a app that was 25mb and it worked fine, so storage is not the issue. I tried clearing data and cache and I still get the message.
I have tried clearing cache in recovery also tried safe mode, removed play store updates. This is not a storage issue or play store issue. I tried installing an apk without using play store and it still failed. I'm rooted.