Hmmm... well first, and this may seem obvious, but reset your phone. If it still does it, try a full-on restore through iTunes. If it still does it, then it's likely not a software problem at that point but rather a hardware one.
Are you near an Apple store? Even if it's not under warranty anymore, a Genius should still be able to tell you what's wrong with it for free (if you're nice to them
). If I remember my Intro to Computer Engineering course correctly, the audio jack sits on the logic board of the iPhone. It can't be the entire logic board because then you'd have many more and much bigger problems. Perhaps it lost its physical connection to it, though. All of this can be determined by the proper technician taking a look at it (such as a Genius or Geek Squad agent). But try the simple, at-home software fixes first and see what happens.