There are a few things you could and should try. The first to rule out the possibility of a faulty/damaged set of earphones.
It might not hurt to also reset your Shuffle as well and then try listening to your music/content again with the old headset and a new one.
Otherwise a full restore of the Shuffle in iTunes will need to follow. See here for instructions on restoring your Shuffle.
A restore will out any other possibilty of a software issue or glitch and will help pinpoint a hardware one if the problem still continues, although it seems that you have already discovered that it appears to be an issue with the actual headphone jack.
I am currently having this issue as well. Turns on, plays 3 secs, song gets crackly like the headphones are bad then song totally disappears. sometimes I can hear a crackly beat if the sound is way up. Then it will intermittently come back with the sound softer and without notice the sounds gets loud.I've held teh iPod, run with it attached to my shirt, walked with it and it does this no matter what. It is VERY ANNOYING and really tells me that Apple's brand is not as good as it used to be if they allow products l ike this to be out there. I've had this about a year and have not used it that much - maybe 30 hours.
It is not the headphones. It must be something inside the jack hole because prior to that happening, my headphones stopped playing on one side.
Puttrick, please let me know if you got your issue resolved, and if so, how. I doubt Apple is going to help with this.