I had a SD card in my phone that was really small...I went to the store to get a larger one so I would have more storage. A lot of my apps and such were on the old SD card. I backed up my phone prior to removing the old card, removed old card, inserted new card, and restored my phone. It is still saying I don't have storage and won't let me redownload my applications. please help!
Clearing cache from recovery (stock should do the trick) has worked for me in similar situations. Try that and see if it allows you to re-download app. Clearing cache forces mediaserver to re-read all the storage space and indexing it.
If you have your apps on internal storage, and install location set to internal, you will receive an error.