SMS on HTC Desire is not working
Both the default Android messaging app and the HTC Sense app are buggy, as far as I've heard.  Until they get their act together, I recommend trying another SMS app and seeing if it's any better.  Handcent SMS would be a good choice.