I HAD the same problem. It wouldn't play anything. Moreover the green light was allways on when in playing mode and did not react to any keypress.
Problem: formatted in a wrong way. (Allthough I really thought I did everything exactly as in the manual, apparently something went wrong)
Sollution: go to apple website or google and look for IPOD UPDATER to reset your shuffle to factory default and update to the latest firmware at the same time. After flashing, remove from computer, put back in, itunes should open, put music back on ipod, go to play mode... and Hopefully your problem is solved too.