Ah, found the cause. The project is owned by another Github account (which I also control). Something must have changed with Circle as it seems to only allow the project owner to ssh in now.
I fixed it by generating a new ssh key for the project owner (ssh-keygen -f ~/.ssh/other), adding it to Github, and using that to connect to Circle (ssh -i ~/.ssh/other).