Just got my G1 today (what an awesome phone
) and was having the same problem.
First text I sent I had to select the number from the contact list and then type the text - only problem was that I accidentally hit enter 5 characters in... there it went!
I had also synced all of my contacts through Gmail, the issue was resolved by making sure that each contact was set to mobile. This is a little odd as when you select a contact through the contacts icon you can send a sms message to any number.