More than a few hundred MB of "Other" indicates an interrupted or corrupted sync. A restore will fix it. Here are the instructions:
http://support.apple.com/kb/HT1414
The backup you make before you restore includes information such as mail settings, text messages, notes, call history, contact favorites, sound settings, widget settings, certain network settings, and other preferences including settings and data from third-party applications purchased from the App Store will be restored from the backup. You music, videos, and applications will be reloaded by iTunes. The only thing you will lose is some time while this takes place.