OS X Yosemite & Time Machine: identity of the backup disk has changed
There seems to be an issue with Yosemite renaming the computer local host by adding (#) after the computer name. There are other reports of this happening in a thread on MacRumors Forum and I believe a few people have blamed this as a cause of time machine backup failures. I've tried a few of the suggestions in the thread but so far none have worked. I've stopped using time machine for now and reverted to an old bash rsync script.

A really simple solution is to open the terminal and type:

rsync -avu ~/ /Volumes/backup_disk/backup_folder


replacing 'backup_disk' with the name of your external hard drive and 'backup_folder' with the name of the backup folder i.e.: 'yosemite_backup'. The three flags -avu mean: archive (a) copy the home directory recursively into sub folders, verbose (v) print to the terminal window everything you are copying (feel free to leave this out) and update (u) will only overwrite files that are newer than the archived file (useful after the initial main backup). This solution isn't as hands off as time machine but at least it's a simple way to back up vital information in Documents and Pictures/Videos.

Edit: 2014/10/28 - I've had success with the following procedure:

Go to Macintosh HD > Library > Preferences > SystemConfiguration and delete the following files:


com.apple.airport.preferences.plist
NetworkInterfaces.plist
preferences.plist


Then remove the numeric iteration (#) from the computer name (or rename altogether) in System Preferences > Sharing and reboot. The plist files will be recreated after reboot. So far this has fixed the computer name issue with Yosemite on my machine and time machine seems to be back on track.

Note: This fix seems to be inconsistent with users and may not fix the naming issue after all.

Edit 2: 2014/11/11 - The above seems to have worked for about 2 weeks but the renaming issue is now back.