I looked at settings and made sure app-password (two factor auth means you cannot use your Google password but the password generated for the app) was correct. There was no sign of any trouble anywhere but clearly it was not sync'ing.
To keep this short; I found out the issue was that I had my Google contacts sync to use 'Exchange' (aka Active Sync). I vaguely remembered that there was some ActiveSync licensing news a while ago and after some digging found two pages of instructions on setting up iOS devices with Google contacts Sync Option.
One from Apple: http://support.apple.com/kb/HT4872 , very short, Apple style, with just the minimum information they could give... (noticed that they are still not using https?)
Follow these steps if you're using iOS 7 to sync your contacts with Google Contacts:
- Tap Settings > Mail, Contacts, Calendars > Add Account > Google.
- Enter the required information in the fields.
- Make sure Contacts is on.
And the other from Google: https://support.google.com/mail/answer/2753077?hl=en
Much more detailed. (E.g. Look at #7 and compare that to #3 above)
They started with this:
Sync contacts with your Apple device
Apple's article did not give me a clue actually but specific 'CardDAV' emphasis of Google kinda told me that my 'Exchange' set up was the culprit. So, I deleted the existing account:
Settings > Mail, Contacts, Calendars > Gmail > Delete Account
The catch is that it forces you to delete all the existing (google) contacts from the phone :(
Anyway, I went ahead and did it. Then, added Google account back and once I launched the 'Contacts' app, sync started and is working fine now.