It would be helpful to know a few things about how the router (or switch) was configured - especially is it doing login local or is it doing aaa - and if it is doing aaa how was authentication configured.
But I will guess at an answer based on some assummptions and if I am not right you can clarify some things.
If it is configured for login local then it is expecting to have a user name and password configured on the router. If there are no user names on the router it gets difficult. Try accessing vty ports via telnet and try accessing the aux port and the console port. If you are lucky one of them might be doing authentication with the line passward rather than login local. If these do not work then I think you will probably need to do password recovery.
If it was configured for aaa then there is a question whether it is going to an authentication server or looking for locally configured names. You might try entering one of the old names with the old password, enter one of the old names with the new password (which is what I think you said you have done), or maybe try a carriage return at the name prompt and see if you get to the password prompt where you can try the old and the new password. And I would suggest trying these not only from telnet but also from connecting to the console and aux ports. If theses do not work then it may be that you will need to do password recovery.
HTH
Rick
HTH
Rick
