I have seen many fixes for this problem and none of them have worked. This started when i started up my phone and Pandora Radio was missing from everywhere. Usually a fix involves clearing the cache or uninstalling and re-installing the application, however I cant uninstall it to re-install it, I never uninstalled it and now it's suddenly gone. So when I try to re-download Pandora I get the "Insufficient storage available" error. I have also searched my SD and connected my phone to the computer to maybe find something of Pandora left over and to no avail. It has completely disappeared.