Hi All
This has been a fairly common problem in these discussions, unfortunately. A while back, I and several others ended up sending our iPods back. Turned out there was a problem with the switches beneath the "menu" part of the click-wheel. The "toggling the hold switch" working in place of the menu button is part and parcel of the same problem. You might also find that the backlight comes on intermittently and you can't switch the iPod off by holding the play/pause button.
If all these things are true of your iPod then send it back:
http://depot.info.apple.com/ipod/