I found this solution online and it worked great (after 12 hours of frustration before I found it, including T-Mobile support saying I had to do a factory reset)
This is a general Android Tip/Fix for Corrupt Contacts or Contacts Not Syncing
Recently, some colleagues in the US received OS updates to their Android Phones, which in turn caused problems for several of them where their Google Contacts stopped syncing to their phones.
This is typically a problem of “corrupt contacts” on the device, and provided all your contacts are in the Cloud, the fix is fast and easy (and I’ve blogged about it back in November 2012…. so I am quite familiar with this)
If the contacts appear OK in Google – via the web-browser, we will simply go into the Android Contacts and “clear the cache” and let it rebuild/resync from Google.
From the main screen, press MENU key–Settings
Select Application Manager (or Applications)
Using the tabs at the top for ALL (apps), find “Contacts Storage” (NOT “Contacts”), select it, then choose “Clear Data” and OK.
Go into your contacts and they should start to sync (or check the Account Properties for the Google Account and do a sync)
Happy Android Phone Use!
Justin Gale