CityCat4

На офицальной странице Putty - единственном валидном источнике загрузок - есть только MSI для винды (32бит, 64 бит, АРМ) и сырцы. Никаких "портабельных сборок" там не ночевало, следовательно, Вас дуют. Закиньте ее на VirusTotal - наверняка там что-то есть :)
Если же ничего нет - значит просто криворукая сборка "от Васяна".

Ну, тут несколько вариантов.

1. Отключен вход для root
2. Для root вход только по ключу
3. Клиент и сервер не договорились о стандарте шифрования.

Последнее очень возможно в том случае, если openssh новый, а клиент старый.

Глеб - искатель проблем на свою ... шею и ... нет, вовсе не первопроходец в этом вопросе :) Не-ASCII символы в логинах использовать не рекомендуется из-за их неоднозначности.

Ну, вариантов немного:
- неверный логин
- неверный пароль
- данному логину запрещено входить с данного IP (или вообще)

В любом случае, если Вы не админ - связаться с админом, если админ - рутом с консоли

Фигаж себе структура. Интересно накуа так? Или второй роутер - не роутер, а просто свитч? IP, маску и шлюз выдает какой-то из роутеров, нужно его настроить так, чтобы он выдавал по маку центоса нужные данные (надо полагать в настройках VB - "сетевой мост"?) DNS можно указать провайдерские или же 8.8.8.8
Что касается ssh - она скорее всего не запущена. Открываете консоль, заходите рутом, запускаете сервис sshd. Если его нет (а такое может быть) - настраиваете сеть, устанавливаете сервис.

Типовая админская работа.

Подключаться с консоли и исправлять конфиг, ессно. А если сервер чужой - сказать об этом. Тыща причин:
- логин рутом запрещен (вообще я всегда так делаю - пусть киддисы пыжатся угадать пароль - они и с правильным не попадут никуда ;D )
- требуется ключ для логина
- логин возможен только с определенного IP или диапазона IP

Данный сервер не поддерживает в качестве метода аутентификации ввод пароля с клавиатуры, только ключи. Я обычно такое ставлю на учетки автоматов, чтобы мудаки умники различные не лезли.

А там точно ssh запущен?
А там точно его пропускает iptables?

Запустить в этой самой консоли sftp куда-вам-надо и выгрузить туда БД

При подключении или после ввода команды sudo?

Connection refused - в соединении отказано. Такая ошибка обычно возникает, если на той стороне никто не принимает соединения, например ssh сервис не запущен.

Возможно путти предлагает хосту набор шифров, который хостом не поддерживается. Это нечастая ситуация, тут должен быть либо очень старый ssh сервер, либо очень старый putty, но такое возможно. Есть у меня сервак под FreeBSD 9.2-STABLE, который не обновляется и уже никогда не будет обновляться - с заходом на него уже есть некоторые проблемы:

> ssh -l user not-a-server.ru
Unable to negotiate with XXX.XXX.XXX.XXX port 22: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1