Mac Time Machine malfunction

After I changed the hard disk to make a new start with my NAS326, my Mac's Time Machine does not let me log in to the TimeMachine folder admin on "NAS326 (Time Machine).local". 
The proposed user name is always wrong, and after changing that to admin and giving the right password, it says: "Time Machine cannot connect to the backup disk. There is an error authenticating with the provided username and password". Not any of my users can log in anymore...
I tried to check and even delete anything referring to my NAS in the KeyChain, also tried to change the location in Backup Planner, both without avail.
What can I do to make Time Machine work again?