I have an HTC Incredible and I have received the "Low on Space" message since October and I have been removing unused applications, clearing the cache, etc.. to get my phone to operate properly. I spoke with someone at the Verizon store and he said that he heard that the error is due to an installed "application killer" application caused a problem with how my phone views memory. I have an 8 GB card installed and have plenty of free available when I view the available space for all types of memory.
The Verizon guy said that I have to do a hard reset and reinstall all of my apps. I was delaying the reset because I didn't want to have to deal with it, but I am finally fed up and will be doing the hard reset in the next few days. Hopefully this will work.