(This is as of TortoiseGit v1.8.3.0.)
Do a "Git -> Git Sync" first in the TortoiseGit context menu. (Note: you may have to hold Shift down as you right click, depending on how you have Git Sync set to show up in your context menu.)
There will be a button in there at the bottom left called "Remote Update". Do that, and it will pull down all of the new remote branches that are not present in your local repository.

After that, you should be able to do "Git -> Git Checkout" as normal, and the branch you want will show up in the list.
I should note that this same procedure can be used to inform TortoiseGit about new branches that have been created in the remote repository, whether you originally created them or not.