My contacts were messed up after activating 4S. I corrected it manually on my desktop but iCloud went viral and kept reverting it back. So I deleted all contacts on iCloud. All my devises are good now but iCloud is a blank. Can you upload to it again?
Try going to settings, iCloud and turn contacts off. Since your iClouds contact list is empty, keep it. It will confirm you turned it off.
Now turn it back on. It will ask you if you want to merge the contact list from your desktop with iCloud's. Answer yes.
Then force an iCloud backup. Your contacts should appear in the contact list on the iCloud site.
Worked for me. Hope it works for you.