Hello, I had this problem. New iPhone 4, got it all set how I wanted which took some time, went to listen to some music and it was like the vocals were really faint and echoey the supporting music was much more prominent - almost like a karaoke mix. After reading all of the comments on your problem and having come across the description of the iPhone 4's 4 jack plug, it clicked that I needed to push the plug in one jack further. Ooops! I had tried this before but the last notch has quite a lot of give to it before it goes right in and being a new precious toy, you really don't want to force anything that isn't supposed to be forced. I know certainly that with one of my previous iPhones - I think it was the first model - it was a 3 jack, but I had a pair of headphones that worked on it but was a 4 jack so it would sit 1 notch up in the socket. This is why I was more sure it was a technical problem with the phone and was dreading having to get it replaced and have to get everything back on the new one how I like it again.
I am sure the apple genius knows what he's talking about when he said that not all earphones work on the i4, I'm sure they don't. But I knew this wasn't the problem as it was the earphones that came with the phone that weren't working for me. Therefore, I might be wrong, but if you're still having this problem and any small part of the jack is showing above the plugs "handle", give it an extra firm push in till there's not metal showing. As long as the plug clicks in 4 jacks (or notches), it won't hurt your phone - honest 🙂