Do you have a different set of headphones you could try, to determine if the problem is the iPod or the headphones?
Make sure you have reset the shuffle, since noticing this problem.
Unfortunately, if you tried different headphone, a Reset, and a Restore, the most likely explanantion is that the headphone jack on the shuffle, or the portion of its logic board that produces audio output, has become faulty.
You can check the iPod's Settings or Summary screen (in iTunes). There is a checkbox there that limits maximum volume; make sure it is not checked and set to an unusually low level. BUT if you did a Restore already, that would not be the problem because it would have been reset to default settings.
(It would still be under warranty, if it's less than one year old.)