As Sarah suggested, it could be that the actual switch is broken. If you pop the back off, can you see a little black switch near the top right corner (top right when the iPod is laying on its face)? If so, is it broken?
It could be that the little hold switch toggle itself got a bit bent out of shape; I've had that happen a couple times too. Just try to bend the pins VERY CAREFULLY back into place.