I just restored my iPod Touch 2G MB with iOS 4.1, and there's still over 200 MB of "Other" space. I even set it up as a new iPod instead of restoring from a backup. Why is it still there?
I was Jailbroken on 3.1.3 before. Could there be something left over from that that iTunes doesn't know how to delete?