Can't download anything from Google play My internal storage has 400+ MB and the SD card has 9 GB left (I know SD card doesn't really matter). I deleted a lot of apps and I still get the message "Not enough space on your internal storage" when I try to download an app that is 7 MB.
This is not simple to solve. The solution that worked for me requires the device to be rooted, "Terminal Emulator" app and a file manager that can access to your whole file system (like "Root Browser"). I also have the "BusyBox" app installed which might be necessary to use the terminal emulator properly.

The first thing I did was to spot all files associated to the app I couldn't install. In my case, I achieved this in the terminal emulator with the commands

su
find / -name "*[some part of the package name]*"


The first command is to gain root privileges in the terminal in order for the find command to be able to search your whole file system. The second gives you a list of files and locations related to the app you want to install. The text in brackets [ ] must be replaced by a part of the name of package which distinguishes from all others. In my case, the package is the FB Messenger. The APK file is called com.facebook.orca-21.0.0.20.13.apk, so I decided to search this way:

find / -name "*orca*"


Then I deleted all the files and directories listed using the root browser (this is a brutal force method, may be it is not needed to delete them all...).

Finally, I rebooted my phone, let it start and installed the Messenger through Google Play Store. It worked :)

I hope this helps.