MySQL Front - Workbench
After reseting root password, I could connect with workbench. I still can't connect with old users (which were already created), but connecting with root and creating new users with workbench allows me to connect with these new users.

It looks it has something to do with the password, or the way MySQL Server stores password for users. I don't know the actual reason for the error, but this solved my problem.

Thanks for the suggestions!