A few nights ago, I updated my iPhone (3G S) to the latest version. Upon doing this I had to resync it. The next day, while putting an album on, I noticed I had 4.08GB of Music and 4.03GB of "other". It occurred to me that this must be my music.
I googled around quite a bit and the only way I could find to fix this was to restore the iphone and resync everything. This in my opinion, is not good enough. Apparently Apple are aware of this issue but have not issued a fix for it.
I would encourage you all to write to Apple and let them know what you think. Contact details can be found here.