I was a long-time desktop (Linux) Thunderbird user, but eventually became frustrated with its inability to automatically sync my contacts with my phone. I use Outlook.com, but this suggestion equally applies to those who use GMail for contacts storage.
I solved my problem by switching to Evolution. I just enter my email accounts via the "Online Accounts" application and then Evolution seems to make everything work automatically. I wish Thunderbird could do this too, as I prefer its interface.