Which MAC Address should be used? Built-in Ethernet, AirPort? I've tried both and when I try a backup it says:

"The network backup volume could not be mounted because there was a problem with the network username or password."

As stated in a previous comment on this very page:

On my MacBook, which uses its built-in AirPort to connect [..] actually the MAC-address of the ethernet port is used (though not active!), not the Mac address of the built-in AirPort (which is active).

And:

To tell Time Machine to use other credentials one needs to clear the network passwords in Keychain -- but until today I did not know that in Keychain's menu View there's an option "Show Keychains", which is required to allow for selecting "System" (it defaults to "login") when searching for the old passwords to change (or simply delete to be prompted for new credentials)...

Does this work for you as well?