Storage help on galaxy s4
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.