Here's a test to perform - using a computer's browser, log into icloud.com and go to the Contacts page. If they are gone, then they are gone (must have been a setting during the update to iOS6).
If they show up, then the problem is that your device is not connecting to the Contacts database on icloud.
On the device, go to Settings>icloud. Be sure icloud is on and using the right ID. If not, scroll to the bottom of the page and tap Delete Account - this just disconnects the device from that account, no data is lost. Then log back in using the correct ID. ALSO - be sure the Contacts are turned on (on the same screen).
Note: Contacts are not part of an iCloud backup, since they are part of contacts database on iCloud's servers. So performing a restore will not help.