More specifically, it sounds like your host upgraded the MySQL server and didn't request clients update their passwords; mysql_upgrade cannot and does not upgrade passwords,
nor does it warn about them needing updated in some versions.
I'm thinking that if you access your hosting control panel and update your password that it'd likely start working again. Basically, older passwords on the machine are stored with a different/shorter hash than what newer passwords are generated as, and in the latest upgrade they're now longer allowing the shorter hash to be used (I believe your host could "fix" this if they'd use the "useLegacyAuth" setting in MySQL).