I've cleared out as many apps as possible, and the phone says I have 14.17 MB of Available space for my internal phone storage. I also deleted all of my text message threads, and I keep getting the "Text message memory full" and the "Low on Space" warnings. I tried following the instructions for booting into Safe mode and it did not work.
I am running the 2.2 Froyo software.
Ouch! Since you have deleted all you text message threads, let's you check one thing. Go to settings > applications > manage applications > all tab. Scroll to dialer storage and see how big it is. If it is > 3 mb, select it and clear the data. It will clear any leftover text message memory as well as the call history. Backup as necessary.
Have you tried the more your apps to the sd card?
Have you cleared the cache out of the installed apps? This includes preinstalled ones like browser, market, email, etc.
You might also want to consider completing a factory reset. It will erase everything on the phone, but the sd card. The phone will look like it should from the factory only with 2.2 installed. After activated the phone again, you should look to see how much internal memory you are starting with before you reinstall your apps.