You should have mentioned that. Proxy servers often have additional caches.
Here's the deal:
1) Gravatar caches. Their cache may not clear for a few hours.
2) Your proxy or ISP can cache. This is not a typical setup but looks to have been the issue in your case.
3) Your browser caches.
To see the updated avatar, you need all caches cleared.