Originally Posted by MacBryce
The best solution would probably be to root the device so you can get apps2sd and move your apps to your external storage (SD card). I haven't rooted my phone, but there are plenty of guides on the net.
Rooting will not cure the problem. I'm rooted and have apps moved to the sdcard, and I still get the error message from time to time.