I just upgraded my iPhone 3GS to iOS 4 (iPhone OS 4) and lost all my contacts. Initially they were there and all was well, but then they all disappeared.
I even had to enter my voicemail PIN for the first time in years (I have never done this since first setting up my original iPhone years ago).
The fix? I’m not sure
For me, I seem to be getting contacts back in. I was lucky to be using a Google account to manage calendar / email / contacts. I removed that account, set it up against as exchange, and then waited. It seems to trickle back in. Maybe everyone that used Google exchange accounts is doing this and slowing down the servers.
I keep checking my favorites list, and see names appearing where numbers were before. Voicemail is filling back up with real names too.
It may help to know that when I was in contacts I saw the “group” link in the top left corner, and selected the “Contacts” option, as opposed to my “domain.com Global” option.
Let me know if you are having any luck.
UPDATE for iOS 5: If you are having trouble on iOS 5 please check out this iOS 5 help article including various fixes for lost contacts.