Когда пытаюсь подсоединится к серваку 
>mysql -uroot -p
то после ввода пароля получаю:
Error 2003(HY000): Can't connect to MySQL server on 'localhost' (10061)

Остановил службу, открыл командную оболочку, сделал команду 
[PATH TO MYSQL BINS]/mysqld-nt --skip-grant-tables
как написано на http://lists.mysql.com/mysql/177981

Заглянул в службы - но там напротив MySQL не написано, что Работает. Почему?
Если нажать правой кнопкой и в выпавшем меню выбрать Пуск, то она запустится.
Что делать?

MySQL 5.0.37, WinXP

попробуй для начала telnet localhost 3306 - соединение должно устанавливаться. 
Если нет, то ищи логи и смотри, что в них - наверняка там будет сообщение о какой-нибудь ошибке..

Судя по всему связано было с работой Agnitum Outpost, отключив его и перезагрузив, смог приконнектится.