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.