No one ever mentions that GitHub use the same key for gist.github.com as they do for github.com, and that therefore they also changed the key for gist.guthub.com and you need to update the keys in your known_hosts for gist.github.com.