Low on Storage and Text Message memory full

It is talking about phone internal memory. The SD Card has nothing to do with it. Try to remove some applications (and if you're on Sprint 2.2 Froyo), moving some apps to SD to free up internal storage. You should keep at least 20mb of phone storage free, less than that and it dumps texts and throws errors.
If you're on VM, you'll need to wait until this spring to get the 2.2 Froyo update, and you'll just have to keep a minimal amount of applications.

I wish I knew, I didn't design the system. This seems to be an issue with Android in general (and can be found in the highest numbers on forums of the smallest memory phones). I will guess it is to allow the OS some room to "breath". Even desktop OS's freak out when the HDD space is too low.

Apps moved to the SD card still have to reside on the phone. For instance, Angry Birds is now up to nearly 17mb in size. Will use about 2mb of internal phone memory. If you are that close, you really should remove some other apps and keep your free space above 10mb (closer to 20mb for optimal usage).

If you are looking at the app you downloaded, and it says "move to phone", the size listed is what is still stored locally.