If you go to Options / Status / Menu /Database sizes, what do you have for Address Book? You should see something like 1027/267.5K, where the first number is the number of contacts and the second is the size of the database. If you have 0/0, your contacts are deleted. Rebooting by itself cannot cause your contacts to be deleted. Something else had to happen. If the numbers are not 0/0, your contacts are still there and may just be filtered. In the Address Book, press Menu, select Filter, and uncheck any box that is checked.
The numbers are 9/3.0K. There were originally no contacts and all of my messages were just from numbers, but one I rebooted again 9 of them mysteriously returned....
I have all of them backed up with Google sync, but as I understand it there's no way to take them from there to my phone.. is that right?