I changed my Gmail avatar image using:
Settings → General → My picture → Change picture
But it only changed below compose, next to my green available dot and at the top left of each email I send. My old avatar image is still used if I hover my name at the top of an email or if I hover over my new avatar image next to my green available dot.
Edit: I tried clearing my cache and I tried different browsers but neither works.
Best Answer
I had the same problem, I had to go into my gmail contacts and delete all the entries for myself. After I did that, voila all fixed. To get to contacts, select the GMAIL button the on top left and a drop down will appear where you can select Contacts. Make sure and remove the contact entries for yourself under "My Contacts" and "Other Contacts".