Solution 1: Verify new contact default account location
It is likely that while Sync is working, that the contacts aren't syncing because you are not creating those contacts in your iCloud account.
The contacts app has the concept of different places to store Contacts, indeed all iCloud services do this, a more relatable example would be in Apple Mail where you have multiple mailboxes within each email account.
One of the options in both of these Apple applciations is to create things 'On My Mac'.
In this case it's likely you are creating contacts on your Mac or iPhone and not in iCloud.
You can check and fix this by:
macOS
- Launch
Contacts.app
- Click "Contacts" in the Menu Bar, then "Preferences".
- Choose the "General" tab.
- At the bottom look for "Default Account"
It should be your iCloud account.
iPhone OS
- Launch Settings
- Tap on "Contact"
- At the bottom look for "Default Account"
It should also be your iCloud account.
Solution 2: Signing out of iCloud and back in again
If the above doesn't fix the issue, or is already correctly set to your iCloud account, I would suggest signing out of and back into your iCloud account.
Warning: As there is unsyncronised data there is the possibility of data loss, you need to manually backup the missing contacts.
macOS
- Launch
System Preferences.app
- Choose "Internet Accounts"
- Select your iCloud account
- Click the - (minus) symbol to remove the account.
- Click the + (plus) symbol to add the iCloud account again.
iPhone OS
- Go to Settings
- Tap on your profile at the top with your avatar.
- Select "Sign Out" at the bottom
- If prompted choose "Sign out of iCloud"
Tip: Don't sign out of both at once as it will make login with two-factor authentication difficult to impossible.