Does your Mac meet these requirements?
Macintosh System Requirements
Mac OS X v10.1.5 or later,
Mac OS X v10.2.6 required to copy photos to iPod Photo
Mac OS X v10.3 required for AirPort Express
400MHz G3 processor or better
QuickTime 6.2 required to encode AAC
QuickTime 6.5.2 and latest iLife updates required to use purchased music in iLife '04
256 RAM recommended
DSL, cable modem, or LAN-based high-speed Internet connection recommended for buying and streaming music
Edit: I find it odd that someone who has shelled out the money for an iPod hasn't bothered to update their OS... maybe that's just me.