Bear in mind that Apple quotes the number of songs you are able to store on any iPod by using the AAC format at a bitrate setting of 128kbps and for a 4 minute song.
Look in iTunes under edit/preferences/advanced/importing. What does it say in settings and import using? You may have the import settings and bitrate set wrong. You need to compress your music using either mp3 or aac. If you see AIFF, WAV or Apple Lossless then those formats are going to take way more space than mp3 or aac, especially the first 2 which are raw uncompressed formats.
See this article.
<a href="<a href="http://docs.info.apple.com/article.html?artnum=60955">How much stuff will fit on my iPod?
And incidentally, a song of the same length, encoded at the same bitrate, gives an almost identical file size whether it be encoded in aac or mp3.
Where the space saving issue comes in is because many people say that if you encode a song at 128kbps in aac format, then the sound quality is as good as the same song encoded at 160 or 192kbps in mp3 format, therefor with aac you can lower the bitrate, get the same (or better ) quality, and store more songs on your iPod.
You can convert your original songs to a smaller bitrate by selecting one in the import options I mentioned earlier and then highlighting the songs in iTunes and selecting "convert songs" from the iTunes 'advanced' menu.