i had problems in which my scroll wheel and menu buttons would not work, or would only work some of the time. i went to the online iPod troubleshooter, couldn't fix it, so then submitted my iPod for repairs through apple's online form. they ran my serial, saw that i was still under warranty, and i had a box to ship them my iPod 2 days later.
i sent her in, and since it was a mechanical problem, they replaced the iPod with a brand new one, engraving and everything (too expensive to repair the little innards of the pod i guess). I had a new, engraved iPod the day after the order was created (all the way from taiwan, i was impressed by this).
try the iPod troubleshooting site over at apple support, then if you (or they) can't figure out what's wrong with it, submit it for repairs. they treated me right.