Avatars are stored as normal images, not served dynamically like a default SMF install does. This puts less load on this server, but some browsers might think the image hasn't changed when it actually has, so will still show an outdated cached version =(
Pressing ctrl+F5 will make your browser do a hard refresh (ignore cache, load everything freshly), which would show your new avatar =).
There's some settings in place from where the avatars are served to tell browsers to automatically force a refresh of the images if it's been 3 days since they last loaded them. Any longer we thought would be more impractical, any less and the bandwidth usage goes up alot. Not that we're short on bandwidth (sup RMRK radio =D), but as it is now, RMRK uses over 5 GB a month
just from avatars =o.
If your new avatar is a different filetype to your old one (say your old is .jpg, new is .png or .gif), you'd see it straight away of course