if u use FINDER on your phone as a file browser you might whant to check TRASH folder in your root ( click on apple icon in top right corner) it keep all files that you delited in this folder so you have to empty trash this was my problem only i had 600 mb of trash files
Is this the same for a 1.1.2 phone? Because my "other" is also increasing, but i don't have anything in the Trash folder. And even if i have moved my Application folder to the media partition, i don't have 180Mb of applications.