Over and over again I was recieving "Server not responding" or "Invalid Host Address" errors while syncing was being processed. All the given solutions on the web are useless: changing database name from "contacts" to "Contacts" and back, or even changing it to"./Contacts"; switching to server version from 1.2 to 1.1; using login name other than full email address; soft resetting the phone — nothing helps.
The solution was found strangely — I tried to sync over GPRS connection and, voila, everything synced. Looking through the router setup I found that there was no default gateway for devices connected over Wi-Fi and IP assigned using DHCP (all the home devices use static addresses) so that Nokia E65 was not getting the gateway I suppose to get to the Google's side.
I don't really think that's the root of all that "Server not responding" or "Invalid Host Address" problems but looking through the router's setup helped I suppose. Moreover, I turned off "uPnP" if that helps.