I know this sounds strange... but... here we go.
1. I did the steps above, and did not work.
2. Even after 30 minutes, I was not getting contacts. My Email and Calendar... no problem.
3. So, I deleted the email account from the phone and set it up again. Still, no joy after 30 minutes.
4. Then, I needed to make a call so I went to my call list and noticed that the names were still appearing in the list even though nothing was in my contacts.
5. I checked the details on the person I needed and everything was there. 6. Then, I went to my contact list and "poof" the contacts were there

.
So, I am wondering if there was a glitch in the contact list and it was not "refreshing" until another application on the phone needed it. Now it is updating and pushing content just fine

.