After some troubled tries I could save (not sync) all my contacts. First try was to remove all contacts again and sync with Mac address book (which is also synced with Google) using Kies (Samsung); it always crashed when around 80% sync task was performed. Then I remove all contacts again, created a vcf file containing all Address Book data, copied it to the phone and finally imported data from file.
Just to check sync with Google I added a test contact to Address Book, synced to google and then synced from the phone. The contact was added despite 'Sync is currently experiencing problems...' was displayed again.