Regardless of how much you have spent, that seems like a small ammount of songs on that large of a space. i have 2.8 gigs currently on the phone just for music, and it is at 694 songs, which roughly translates to 1000 for every 4 gigs i use. So you "should" be able to set aroud 4000 if you are lucky. but that is just by my estimate...
for some, being a cop means they WILL do it because they can get off easy. not saying this is the case but i know a few cops around here that like to throw their badge weight around.
but basically my friend has a 16GB ipod touch and i have a little over 4000 songs and she had to go through every song and pick what she wanted for a playlist because they wouldn't fit.
The newest version of iTunes has an option to send music to the iPhone in only 128k bitrate. iTunes will do the conversion on the fly (the songs in your library retain their original bitrate). If you are using the stock earbuds, you shouldn't be able to tell a big difference. At 128k bitrate, the OP should be able to fit his entire library onto the iPhone.
In iTunes, the option appears in the main screen when you connect your phone to iTunes (the same screen where you "check for updates".
Good if you are interested in quantity of music instead of quality of the individual files.