If you are using vagrant, you probably-statistically are using git. Make sure you have its binary folder on your path, because that path contains 'ssh.exe'.
Now, modify C:\vagrant\vagrant\embedded\lib\ruby\gems\1.9.1\gems\vagrant-1.0.3\lib\vagrant\ssh.rb
to comment out the faulty Windows check and add a real SSH check:
# if Util::Platform.windows?
# raise Errors::SSHUnavailableWindows, :host => ssh_info[:host],
# :port => ssh_info[:port],
# :username => ssh_info[:username],
# :key_path => ssh_info[:private_key_path]