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:

1. Put your phone on charge.
2. Make sure you are connected to the internet via WiFi.
3. Go to Settings -> iCloud. Turn on Contacts.
4. Now go to Backup -> iCloud Backup: ON
5. If your iCloud Backup is switched on, you get a Back Up Now button.
6. 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.

It's likely Apple can support you with iCloud if your account has a problem. Before calling them, though you will want to check and see under the Settings app what you have configured under Mail, Contacts, Calendars.

It's entirely likely your iCloud contacts are exactly what https://www.icloud.com/#contacts shows.

1. Make a backup of the phone to a computer if possible
2. Make a backup to iCloud for safety
3. Then inspect all accounts. Write down each account that has contacts synced.

You can disable iCloud contacts on the device and tell it to delete all those contacts from your phone. You will then be left with contacts on the device itself and other cloud services. Check them similarly (log in online) and then disable syncing. At the end, you will have contacts that exist on the phone only.

Sync them over the computer and get them into iCloud or enable iCloud only for contacts and choose to merge things.

That usually sorts things out.