We see this quite a bit and thought it would be worthwhile to add an FAQ on the matter.
We pull everyone's avatars straight off of GitHub's CDN infrastructure. We've noticed that sometimes it can take a while, even a couple of days for that change to both propagate across all of GitHub's various CDNs and get out of browser caches as well.
If you are using Twitter to sign in, there is currently a bug where we don't update the user info after signing in again, https://gitlab.com/gitlab-org/gitter/webapp/issues/1834. You can send an email to firstname.lastname@example.org with the details of your rename and we can manually update it.
Rest assured, it will in time update. Unfortunately there's very little we can do about this.