I have tried to install various programs from the Android market and my phone is giving this error. I have over 70MB free and the programs I am trying to install are small (i.e. 5 MB)
Move your downloaded apps to your memory card. Menu/settings/applications/manage applications. Then just go through every downloaded app and tell it to move to the memory card. Some times it might error. Just try again if that happens.
Also check your dialer storage--mms can really bloat your internal storage. If your dialer storage is bigger than 50MB, then you should try deleting some of your text threads.