If you don't know, when you upgrade your mac, your Time Machine existing backups will not work with the new system. Apple's intention is to apparently force you to format your external disk, or manually delete your existing backups, and start Time Machine (“TM” from here on) anew.
Steps are published all over for how to do this, but they all seem to be missing one component from what I've found with Snow Leopard- namely that the xattr attribute must be entered in ASCII Hex for things to work properly.
Also, Snow Leopard does not include the binary fsaclctl, which is necessary to update the settings on the Time Machine disk. You can either try to find a copy of fsaclctl online, or find out what command has replaced it. If you obtain a copy of the fsaclctl binary, copy it to your /usr/sbin folder.
Steps to get your existing backups working again are essentially:
Steps in detail:
cd /Volumes/TM
where “TM” is the name of your TM disk
cp .0016cb9268a5 .0016cb9268a5.bak
xattr -l Backups.backupdb/systemname >> ~/systemnamehex.txt
Where systemname is the name of your system disk.
ifconfig en0|grep ether
sudo fsaclctl -p /Volumes/TM -d
cd /Volumes/TM