I've been getting the warning for the last few weeks but have been able to make it go away by clearing the cache for all of my apps. That's no longer working; the warning is present all the time, even after rebooting. This, despite my phone still having 549MB (73%) free and my SD card still having 6.62GB (44%) free.
In my case, Gmail is no longer syncing -- so I *can't* ignore the warning any longer.
I guess I'm to the point again where I'll have to wipe the phone. This will be the third time I've had to do it within 11 months. Quite a pain, but it's been an awesome phone for me, otherwise. Wish we could get some official explanation from HTC and/or Google as to why this occurs, what they are doing to fix it, and what we can do to prevent it in the meantime.