Their instructions could stand to be more thorough. If you have hashed hostnames in your known_hosts, you don't just have to

    ssh-keygen -R github.com

you also have to

    ssh-keygen -R 140.82.121.3

which is the IP address for that host. Otherwise you'll get something like

    Warning: the RSA host key for 'github.com' differs from the key for the IP address '140.82.121.3'
    Offending key for IP in /home/tom/.ssh/known_hosts:77
    Matching host key in /home/tom/.ssh/known_hosts:102