Allow iTunes to sync down-convert your music to 128k AAC and you'll have plenty of space.
Be ready for them to sound terrible though.
Here is what i have on my 16gb model.
Songs 808
Videos 0
photos 11
applications 17
I have got 1.3 gb space left!
All my tracks are 320kbs. It depends on how serious you are into your audio what bit rate you want your tracks at. If i downsized to 192 or 128 i could get a lot more but at the cost of audio quality which i wont do!!