It could also be because you did as ATT says to do, which is backup your contacts to your SIM card. I can't say on your specifically, but mine was the same way, and the cause was the SIM card contacts being displayed along with my gmail contacts which were syncing from the cloud.
Even if I unchecked the tick box to NOT have the SIM contacts show, it was still using them to resolve, so the names that I fixed on gmail were not showing, etc.
The fix was for me to ONLY show the SIM contacts, and delete them all one by one, clearing my SIM card. Then my gmail contacts are nice and... Cingular (hah!).
With a properly synced Android device to gmail, there is no need for backing up to SIM that I can see. In fact, you are saving yourself a headache if you don't.