В общем решение нашёл сам)

На всякий случай, вдруг кому пригодится, последовательность действий:
1. Делаем DROP DATABASE `mysql`; тем самым убив всех юзеров и все права. Можно наверное и без этого, но второй шаг у меня с уже готовой таблицей не заработал (наверное из-за разных версий mysql до и после переноса БД mysql).
2. Запускаем из консоли mysql_install_db который эту самую табличку создаёт.
3. Заходим mysql -u root и выполняем

GRANT ALL PRIVILEGES ON *.* TO 'root'@'localhost' IDENTIFIED BY 'new_pass' WITH GRANT OPTION;
FLUSH PRIVILEGES;

4. Рестартуем: service mysql restart (если не получается, то killall mysqld && service mysql start)
5. PROFIT!