"Low on space - Phone storage is low"

[jsh1120]

Delete the cache and (if possible) the data associated with your email and messaging apps. The low memory notification will go away. (If you're using gmail, be sure to delete the cache associated with "gmail storage." You'll have to filter:all in Manage Applications to see it.

 

[LiquidEuser]

Hello Droids!
This may be the answer especially if you have alot of synced emails in your inbox. Clean out your inbox and delete old messages because your phone is uploading them. I had 6700 (141MB) in my inbox, my phone is primarily for business use, so I only have my bizemail synced. This solved the "incoming message rejected" problem. And "Low Storage" problem.