I never had an issue with authentication. My issue was a typo in sudoers (I allowed a user to view syslog, iirc, and had a semicolon instead of a colon) that prevented me from using sudo, as only my primary user was allowed to log in via ssh. Fortunately cloud vps still has vnc login, and I actually had a root password. Now I use a root shell to edit sudoers, so I can test it before dropping root.