In regular view, which is used by the vast majority of viewers, avatars next to posts are hosted on a separate server from other things most of the time to help with server load. The two servers sync only periodically, so that's why avatar updates usually take a while to go through. (Note that the avatar on your profile page is hosted on the main server, so you can also check that to make sure the change went through.)
In iPhone Friendly view, avatars next to posts are hosted on the main servers as well, so they update immediately.