I know this thread is old but people keep adding to it so here goes. I finally discovered my problem with my garminfone being low on space. I found even after clearing cache, deleting apps, etc. I still got the message, which never happened early on. I discovered a bunch of apk files located in /data/cache. I had to root my phone using z4root and superuser along with the DiskUsage app. But once I found the culprit I started deleting these apks. They show up whenever I update an app. I've not found a conclusive answer yet on if I "should" do that but my apps are still working and I've got plenty of space for new and existing apps now.
The problem seems to stem from the fact that the /data folder is actually a separate partition. So no amount of removing mp3s or anything from regular user accessible places will help, you have to remove stuff from /data. It's compounded by the issue that the garminfone doesn't have 2.2, which is when Google first allowed installing apps on the sdcard.
Anyway, that is the key for me. I routinely go delete apks in that folder.