I did notice that in /var/log/messages that user logs on with uid=0.
Well, that's probably your problem unless you've got a weird setup.
1. ONLY root should have uid 0
2. best practice is NOT to allow remote root access, as this is first thing crackers/script kiddies go for.
Create a second acct with secure passwd and 'su - ' from there.
Normally remote root login is disabled /etc/ssh/sshd_config "PermitRootLogin no"
3. normally a user cannot re-use the same passwd, especially immediately. If you need it never to change/expire http://linux.die.net/man/1/chage
& set --expiredate=-1 as per that page.
See also http://www.thegeekstuff.com/2009/04/...ion-and-aging/
See also /etc/login.defs
4. only root would use the format
to change another user's passwd.
Normal users can't do that; they should just say 'passwd'.