As previously mentioned, GitHub is transitioning to a new API and will be soon deprecating the version that Review Board speaks. We've been hard at work on this move (which brings with it a better repository configuration experience and the groundwork for tighter integration with GitHub and other services).
In the meantime, new users have been unable to link with private GitHub repositories, since GitHub no longer supplies the required API Token anywhere on the account page.
But good news! There is a workaround. If you have curl installed (common on Linux), you can request your API token by doing the following:
$ curl -u github_username https://api.github.com/legacy/token
Enter your password when prompted. The result should show you your API token, which you can paste right into your repository configuration page.
We'll be sending out a release soon that will make it easier to get your API token when configuring the repository, followed by a new release with the GitHub API v3 additions in the following week or two. We want to make sure it's rock-solid first.
If you have any questions, we're always available on our mailing list.