Как поменять пароль у root'a в mysql?

Всем привет
При установка mysql

sudo apt-get install mysql-server

Должен запрашиваться пароль для рутового пользователя, но у меня почему-то не было этого.
Т.е. сейчас можно зайти в БД через терминал

sudo mysql

Но как мне подключиться к бд удаленно, например, через рута, если я не знаю его пароля?
Посоветовали утилиту mysql_secure_installation
Установил новый пароль, перезагрузил сервер, но опять при попытке подключится через рута

mysql -uroot -p

после ввода, установленного пароля, пишет аксес динаед
Поэтому возникает вопрос, как можно еще поменять пароль и почему вообще так происходит(почему при установке не было ввода его)
Заранее благодарю за ответы
P.S. Простите, если описание корявое :)