I do not have this MP3 player, so I am going to do some guessing based on similar type devices I have messed with. There are sometimes hidden screws under labels, or behind the battery. But, usually, you will have to pry open the case. There are special pry tools out there that can be used so you don't mess up the case. Look around the net for instructions to replace the LCD screen on popular devices and you will get some ideas (you might even find some instructions for your mp3 player).
Once inside, you might find some small, fragile flat cables, or other wires to go between the lcd, and the buttons on the front of the case. So, when you start to pry the case open, take care that the case does not fly open too quickly.
Once you get inside, you might get lucky and find that a cable has come loose. But, most likly, the headphone jack is attached directly to the main circuit board. You will want to look where the pins from the headphone jack are soldered onto the circuit board. There is a good chance that the solder connection broke due to a cold (bad) solder joint. IF this is the case, it should be fixable by re soldering the connection.
Another possibility is that one pads on the circuit board where the headphone jacks was soldered onto "lifted" or broke off of the circuit board. In that case, it is still sometimes possible to fix it by following the trace on the circuit board from where it broke to where the trace connects to another component. Then, using a very fine wire, connect the headphone jack to that point. However, unless you are skilled at soldering, and have good equipment, this type of repair can be difficult (beyond my skills to be honest).
If you have totally given up on getting the store you bought it from to replace it, and Samsung cant help you (or you decide it is not worth it), it can't hurt to crack the case open and see what things look like.
If you don't care about some nicks on the side of the case, some small screwdrivers, or some other thin prying device should get you inside. Once inside, you should be able to see what broke and then decide if it is within your skills to fix. Being that you can get it working by giggling things around a bit makes it sound like a loose connection or possible cold solder joint, so I would give it a shot.
Just for kicks, have your tried another set of earphones? I have shad a MP3 players where the case actually prevented some headphone jacks from properly seating all the way.
Of course cracking the case open will void any warranty, but, it sounds like there isn't one anyways...
Good luck! Let me know if you have any success.