I got the same message yesterday also. The phone says I still have 22.82 m of space left but I keep getting the message even after I uninstalled a few apps.
How much space of internal storage do I have? Can I move some apps over to the SD card which has 12 G left (have 2.1OS)
Thanks for the help
One thing to note; if you're using a non-Gmail email service (I use hotmail); when you delete an email it remains on the phone in a trash folder. You need to also delete it there to get it off the phone (and it's not on the SD card). I was getting the low space message until I deleted my 5000 trashed emails. Actually, I deleted the email account and readded it. Droid doesn't allow mass deletes.