Are the headphones plugged all the way in meaning the white part of your headset (or whatever color they may be) is flush with the body of the iPod? The iPod has an autopause feature that kicks in whenever it no longer detects the headphones.
If that isn't the case, have you tried a hard reset? To do this, first make sure the hold switch is in the off position, then press and hold both the Select (Center) and Menu buttons together long enough for the Apple logo to appear.
Otherwise, a restore of the iPod in iTunes will be your next step.