There is a better and faster solution than downloading/uploading the VHD. As mentioned, the problem "was recognized to be a missing newline in the sshd_config file!"
0. The first step should be different though, because otherwise you can lose your current Cloud Service IP, if you delete the last VM in it - and on web server this is a serious problem. So, FIRST, create a new VM in the same geographic region as the troubled VM, so the Cloud Service has at least one running VM and your current IP is retained.
Delete the troubled VM but do not delete the associated disk. (You must delete the troubled VM to free up the lock on the associated disk which we would be using later). Note the name of the associated disk (AD).
Select the new VM -> dashboard -> Attach -> "Attach Disk" (Note that the "Attach Disk" option is available only when the associated disk of the troubled VM has been freed up)
Choose the correct AD name in the popup that opens up.
Now SSH into the new VM and mount AD:
sudo mkdir /tmp/dsk
sudo mount /dev/sdc1 /tmp/dsk
(AD would typically be /dev/sdc1; if it isn't in your case, you can find it out by sudo cat /var/log/syslog | grep scsi and looking for the name preceding the message "Attached SCSI disk")
- sudo nano /tmp/dsk/etc/ssh/sshd_config
In our case, at the end of the file, we had a setting "UsePAM yesClientAliveInterval 180" - clearly a newline had been erroneously removed by the upgrade after "yes"! So we inserted the newline, saved the file and followed the steps below once sshd_config had been restored.
(You may also want to do a diff between /tmp/dsk/etc/ssh/ssh_config and /etc/ssh/sshd_config to see if any other configurations are off)
Back to the Azure dashboard: Select the new VM -> dashboard -> Detach Disk and detach AD
Fire up a new VM similar to the troubled VM: + New -> Compute -> Virtual Machine -> From Gallery -> My Disks -> AD (AD should show up here)
That's it - hope SSH works now!
Source answer at the bottom of: http://social.msdn.microsoft.com/Forums/en-US/54c600c0-f4d6-4b20-ad87-1358fa10d27a/linux-vm-ssh-connection-refused?forum=WAVirtualMachinesforWindows