I got this issue, then I removed applications, cleaned the cache, etc., but I was not able to get rid of this annoying message. When I cleaned the "data" on the "Engine email" application, the message was removed... yestarday I got that message again, and notice that it appeared when I received an email with an attachement of 15Mb, I deleted the email and cleaned the data again, and I got rid of the "Storage Full" messsage again.
Then, I believe that this is related to huge attachments in emails, if you delete the huge email, for some reason the data is still stored in the phone memory, you need to delete the data manually...
Hope this helps