Ok, I was told my problem was that my headset was not a Palm headset. I went to the store and tried out the headset that you get with the Pre, and I had no problems. I then tried out a bluetooth headset, and not problems again. So I bought the bluetooth headset.
ronpaul - I think your headset is faulty and the Pre isn't recognizing it. I bet if you go to Sprint, they'll swap it out for you.