TL;DR: If the user with the username you want is inactive, report it to Github on his profile. It's part of their name squatting policy, and you'll probably receive feedback.
It's been a long time since I've wanted to change my Github username, and I had the perfect candidate: 5 letters, exactly my nickname, and easy to say it (well, at least in portuguese...). But, unfortunately, it was already taken.
After reading about Github policies, I found this one telling that my long-desired username might be possible to get, since the user that had it previously was not active and his displayed e-mail address didn't exist (as I tried to contact him).
So, with a bit of hope, I've reported him explaining that the user was not active (didn't have any repositories nor activity in the last 5 years). One day later, I received this:
Instantly I've made the switch! I was already aware of the downsides (gists and mentions to you are not updated), but I've decided that it was worth it.