Not sure you need to restore to remove the "Other" for every case.
I noticed 300mb of "Other" after a sync once (I sync several times a day, and don't pay much attention to the capacity bar normally).
I just resynced and it went away (I think it was actually supposed to be "Music" but was showing as other the first time I synced... I had just changed some playlists around and had synced about 300mb of new music to it).
It may just be that "Other" is anything new you just sent to the iPhone, and that it places it in the proper category the next time you sync.
So before you go do a full restore, eject the iPhone, remove it from the dock, dock it again, and sync again. If multiple syncs don't clean up the "Other" category, then do a restore. But trying the sync first might save you some time.