No Other Category, big "Applications"
Mine does the same thing, (iPhone 16gig 3g-S), having no other category. However, it is still there, because "other" is just your email, notes, and other stuff. So, the only way to fix this, is to delete your backups, unplug your phone from the sync cable, and reset the phone. Then, plug it back in, and re-sync it, and re-set it up again. I know this sucks, but when you back it up from a previous backup, and the backup didn't have an "other" category, then you're not doing anything different. Before you do any of this, MAKE SURE you back up your contacts with google or windows or whatever first. You will lose your text messages and stuff, but at least your syncs will be normal.
I've also had it sync and my "other" category is HUGE! like 4 gigs. Same thing. Reset it, delete backups, and set it up...again. It kind of upsets me that Apple is putting the new Windows 7 down so much, claiming every version of Windows has had problems, and that this one will be no different. When they can't even get a syncing problem fixed. I've had this problem since iTunes 7 and OS 2.1, so as far as I'm concerned, Apple needs to keep their mouth shut. Good luck.