I've been having some very buggy issues with iTunes on the iPhone 3g

It will sometimes stop in the middle of a song. Sometimes the song will re-start a second later, sometimes not. I've had the same thing happen while watching videos.

Sometimes iTunes won't even be open and it will just start playing a random song. If I try to pause the song and exit iTunes, it will just start playing the song again seconds later (I like Justin Timberlake's "Sexyback" as much as the next person, but I felt like I was being haunted).

I took it to the Apple store (after I had to wait a day to get an appointment) only to have the so-called genius tell me to do a restore. That didn't help.

Anyone else having this problem? Any suggestions?