As far as I can tell, this is a bug in WSL. Hopefully, Microsoft will fix it in the next build. But for now, we can use this slightly ugly hack.
Update #1: Definitely a bug. Found this issue on Github. Thier proposed workaround of relaunching the shell works for me as well if you don't want to go through all of this.
TL;DR Add this to END your SSH config (usually located at ~/.ssh/config):
Host *
ProxyCommand nc %h %p %r
Here's why it works:
Our SSH issue is not a firewall issue because nc and telnet work to the same host and port (try telnet <host> <port> or nc <host> <port>: you should see something like SSH-2.0-OpenSSH_6.6.1p1 Ubuntu-2ubuntu2.7). This we can use to our advantage.
SSH allows the use of proxies that take standard input and send it to the server's port via the ProxyCommand option. This is normally used to tunnel into networks to a protected host by using an in-between bastion SSH server, sometimes called a jump host (see this link for more info).
This hack tells SSH to use a proxy with no jump host(s). So, it gets around SSH's failed allocation of TCP resources by pushing all of the network resource allocation onto Netcat, which does work. SSH just does its SSH thing without any network connections, and Netcat sends the raw data over a TCP connection to the SSH server.
WARNING: Since this modifies the ProxyCommand for all hosts, I do not know how it interacts with other SSH config hosts that use ProxyCommand. I have a few servers with which I can test this, and I will update this answer with the results. There is a chance that there are no detrimental side effects, but I cannot guarantee that.
Update #2: I did some testing with a few of my servers, and this appears to work. SSH uses the uppermost entry in the config when multiple entries apply. Thus, an existing ProxyCommand present above this hack would override it. When the new SSH command is executed, it re-reads the SSH config, and if there is no other ProxyCommand, SSH uses our hack ProxyCommand, allowing it to only apply to the "outermost" SSH session. Word of warning: if you put the hack at the top of the config file (or above the entry you are trying to SSH to), SSH sessions that require a ProxyCommand will ignore the other ProxyCommand and instead attempt to resolve the address of the host and connect directly with Netcat.
Best Answer
Windows doesn't have built-in tools for ssh, sftp, scp, etc. You'll have to install something like cygwin or invoke other external tools like putty with a command. It does have a telnet client though, so if your linux server is local (and security is not an issue) and it allows telnet, you could use telnet from the Windows command line for a painful experience.