I had the same problem with my new iPad. I sent it in and they sent me a new one back and guess what? Same problem.
After speaking with tech support again, one guy suggested that I restore as a new iPad rather than restore from my backup, suggesting it was one of my apps.
So I did this and it worked. One of the keys to this being the culprit for me was that the system sounds still worked fine! By system sounds, I mean the basic alerts, mail swoosh, keypad tones, etc.