Only half of my contacts from iPhone 4 sync to iCloud
Contacts app have groups of contacts, ie. Google contacts, Hotmail contacts, Facebook contacts and then iCloud contacts. To see the different groups, go to Contacts, at the very top you will see Groups, just tick iCloud and untick the rest. Now scroll down to the bottom and see if you have 500 contacts or 203.

If you have 203, it means that all your contacts are there. If you still see 500, make a manual backup:


Put your phone on charge.
Make sure you are connected to the internet via WiFi.
Go to Settings -> iCloud. Turn on Contacts.
Now go to Backup -> iCloud Backup: ON
If your iCloud Backup is switched on, you get a Back Up Now button.
Tap the Back Up Now button to manually back up to iCloud.



  Automatically back up data such as your photo library, accounts,
  documents, Health data, Home configuration, and settings when this
  iPhone is plugged in, locked, and connected to WiFi.