I've done a clean re-install of OS X 10.6 and re-installed my core apps, the rest can come over time... I then restored my documents, music, films and pictures folders. I didn't restore Apps, System or my libraries and other settings. This seems to have cured all of the performance problems and the problem with Flash refusing to run.

However, TimeMachine won't now use the TimeMachine external volume, it just claims that it failed, no error messages, nothing... I am assuming, because I did a fresh rebuild and I haven't restored the settings and system libraries, that it is complaining, because they don't match - it tried to back-up 99GB, then failed...

Do I just need to wipe the TimeMachine volume and then point TimeMachine at the newly formatted drive?

Yes, erasing the external HD and starting from scratch should sort it out - before doing that, though, make sure you have everything you need from the old Time Machine backup first. If necessary, buy another external HD for the new system (or borrow a spare one to put you on until you can be sure you don't need anything from the old one).

I think Time Machine links the backup to a particular system, presumably reading a preference file somewhere in the Library folder (or maybe MAC address?) and re-installing the system can mean Time Machine doesn't recognise the old volume anymore.

Formatting and resetting Time Machine should sort it out.

It can't be the MAC address, as this is the same machine, just re-installed...

I had prett much drawn the conclusion, that I need to erase the existing TimeMachine drive. Still, it is a new drive (1TB), I still have the old 250GB WD MyBook drive in the corner, with the old-old TimeMachine backups...

Time Machine doesn't restore the point releases, so if you're on Snowy you need to download the .4 cumulative update. It took me a while to realise after I restored from TM before...that could be why TM doesn't want to work.

I had updated OS X to the latest patches, before restoring my data, but it didn't want to know about the TM drive, I assume, because I only restored my data and not the whole system.

Edit: Reformatted, but it is still refusing to backup, just get the message, that there was an error, but not what error!

Have a look in Console.app ?

Nothing, only thing in the last 12 hours is Firefox NoScrip messages about null Styles.