Original iphone ipod function keeps stopping and skipping songs

I got this 4GB iphone just a few weeks ago as a replacement from the Apple store. I've used the ipod function extensively before today (just even in the last few weeks) but it's now acting like it's possessed. It started when I was in the gym today and after a 35-minute workout, it stopped playing. I thought it was just the vibration that caused it to stop so I replayed another song and it kept stopping and going. I have read other users of 3G iphones having similar issues and some suspect it's the headset jack but mine has nothing to do with it. I restarted my iphone and sometimes it solves the problem but after a few songs it starts acting up again. Now it just randomly plays songs for about 3 seconds by its own choosing. I can't even stop it. It's like it's on shuffle except it only plays 3 seconds and then it stops once in a while and shuffles again! I've pwned my phone as I actually live overseas but do have a legitimate AT&T contract. Does anyone know whether I can fix this by doing a restore and repwning my phone? I don't have access to an Apple store here and would really hate to have to send it back to the US and not have the phone for a couple of weeks. BTW, I've never dropped the phone or damage it in any way.