I am having the same problem as CannibalAngel and have taken all the mentioned steps to try and fix it. I have not tried clearing my cache however because when I go into the "Manage Applications" section and select any app, it says the cache is at 0.0B and the "clear cache" button is darkened so I cannot select it. Is there another way of clearing a cache?
CannibalAngel - have you found a solution yet?
The main cache to clear seems to be for your internet browser. I use Dolphin - you should see a 'manage space' button for your browser in the manage apps section. click on that and you shoud see the option to clear cache. I also chose to move my cache to the sd card.
I am still getting the low space message from time to time. I still can't tell if it's actually due to something or a system glitch. Either way it's annoying.