I've been struggling with the "Low on space" warning for the past few weeks, too. When it occurs, Gmail no longer syncs and Marketplace installs/updates hang. Rebooting temporarily clears the warning and automatically installs the Marketplace updates that were hanging. But then the warning and the issues described above inevitably re-appear.
According to Menu > Settings > SD & phone storage, I have *plenty* of free space:
Internal phone storage
Total space: 6.46GB
Available space: 6.23GB (96%)
Phone memory
Total space: 748MB
Available space: 449MB (59%)
SD Card
Total space: 14.83GB
Available space: 12.88GB (86%)
I followed the suggestions in
What Should I Do When My Android Runs Out of Space for Apps? (moving all cooperative apps to the SD card, clearing the cache for apps, verifying that none of the apps are taking up large amounts of data, and uninstalling unused apps), but it hasn't helped.
Does anyone truly know what is causing this? Is it a matter of not enough "phone memory"? I have 59% free! Or is this perhaps being caused by some other vague threshold being reached?
Very frustrating!