tumbleweed's answer was the only one that helped me. I was dealing with what could possibly have been a corrupted root user and none of the standard methods resolved the issue of not being able to log in as root.
Using the debian-sys-maint user, I was able to finally log into MySQL with escalated privileges and even then resetting the root password did not work.
However, I was able to recreate the root user:
DROP USER 'root'@'localhost';
CREATE USER 'root'@'localhost' IDENTIFIED BY '<newpassword>';
GRANT ALL PRIVILEGES ON *.* TO 'root'@'localhost' WITH GRANT OPTION;
FLUSH PRIVILEGES;
... and finally all was right with the world again!
I hope that helps a desperate soul out there...