This may sound obvious but it had me puzzled for a minute:
When you change your password on a Mac OS X Server hosting TimeMachine, you need to re-enter the password for TimeMachine explicitly on all the clients that use this password. It is not automatically updated with the AFP keychain password for the server. (it has a seperate KeyChain entry from the AFP password, because it is stored in the system keychain).