It fixed the problem on my Evo. Though for the last step, recheck background sync, the auto sync did not make a full sync with the Google contacts. I found that I had to go into Settings, select Accounts and sync, and select Google-Sync contacts. That completed the process and all of the contacts are on the Evo.
i had the same problem on Note. First, I closed my contacts. Then I opened my web browser on my mobile device. I navigated to https://accounts.google.com/Login and re-logged in (re-connected to the server). Then I was able to sync my contacts. It would seem that some how I had become disconnected from the server that supports GMAIL and contacts. It worked for me.