O problema é provavelmente devido à autenticação de soquete sendo habilitada para o usuário root por padrão quando nenhuma senha é definida, durante a atualização para o Ubuntu 16.04.
A solução é reverter para a autenticação de senha nativa. Você pode fazer isso fazendo login no MySQL usando a autenticação de soquete fazendo:
sudo mysql -u root
Uma vez logado:
ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'password';
que reverterá para a autenticação de senha nativa (antiga padrão).
Agora use senha como a senha sempre que exigido pelo MySQL.
