for the past several weeks both my iPhone 4 and iPad have been having this issue, little by little, 'Other' keeps taking up more and more space on my devices. Since I got my iPad in April and iPhone in August, I have been upgrading to the newest software, and if i had to do a restore, I have been restoring from a back-up because I didn't want to loose my App Data.
So last night I was syncing my iPhone 4, and 'Other' jumped from .50mb to .75mb, then down to .45mb then finally to over 1 gb, all in 1 sync, and all I did was add 1 new album and a few apps. So I did some research and found a few sites that claimed that the OS maybe corrupt, and that the only way to fix it is to do a full restore and set up our phone as new (not from a backup).
So I did this last night and what was once before .50 mb now is .25, with the same apps/music/photos as before.
I have yet to restore my iPad, but 'Other' is almost 2gbs, so I think I will be restoring it later as well.
*My iPhone and iPad have never been Jailbroken.