I was worried the server was hacked, I was logged in already as root but couldn't login to CPanel or a new SSH session. I even reset the password from the shell and it did not work still.
The reason is CPanel Hulk, it detected a brute-force attack so it locked down the root account entirely even from the correct password. According to cPanel the best way around this is to whitelist your IP.
http://forums.cpanel.net/f5/password-not-working-whm-cpanel-root-administrator-297262.html
I was aware of CPanel Hulk but didn't know it completely locks an account even if the password is correct from non-offending IPs so this is something to be aware of, someone could potentially create a denial of service against any of your services/accounts just be intentionally bruteforcing them.
The most practical quick way is to just disable cpHulk:
cpanel, vps, server, login, rooti, hacked, logged, couldn, ssh, reset, password, shell, hulk, detected, brute, whitelist, ip, http, forums, whm, administrator, html, didn, locks, offending, ips, potentially, intentionally, bruteforcing, disable, cphulk, realtechtalk, disable_cphulk_in_cpanel_if_you_cant_login_even_with_the_right_password, articles,