This is a particularly involved problem on Windows, where it's not enough to just chmod the files correctly. You have to set up your environment.
On Windows, this worked for me:
Install cygwin.
Replace the msysgit ssh.exe with cygwin's ssh.exe.
Using cygwin bash, chmod 600 the private key file, which was "id_rsa" for me.
If it still doesn't work, go to Control Panel -> System Properties -> Advanced -> Environment Variables and add the following environment variable. Then repeat step 3.
Variable Value
CYGWIN sbmntsec