It seems like the amount of available phone memory you have isn't the issue. When I first got the message, I checked my usage and only had around 10 MB available. Since then, I've followed all of the suggestions for deleting cache, removing unnecessary apps, etc. and now I have 38 MB available, which still isn't much. Something is using a lot of space, but I don't know what. Also, it seems like a lot of other people have plenty of phone memory available, and still get the same problem.
I don't have root (and can't get it currently because I can't install a terminal emulator or any other app), but I think I saw somebody mention that there is a separate section of /data/data that might be filling up. Could somebody confirm this? Also, could somebody explain the partition structure?