Bit late now, but I can add some info to this.
Toms takes a bit to update avatars even if the moderator approval of said avatar is instant, I myself ran into this issue when I was making my current avatar. You pretty much have to upload and wait for an hour or so for it to actually update. Going from no avatar to one is instant though, the avatar is applied even before approval actually.
As a side note, make sure that the image has a different file name to the previous one.