Hello VictorNYC:
Ok!
So, here's the drill:
If I'm not wrong you have 10.5 on you're Mac and 10.6 on you're external HDD [which you converted into a Time Machine], right?
I still think it's a compatibility issue. Now, my suggestions goes has followed:
1) Boot you're Mac without the Time Machine.
1.1.) Once you access the Desktop, insert you're Snow Leopard DVD;
1.2.) When the Installation DVD starts, it will open a Window. Click on the install icon! INSTALL SNOW LEOPARD! This is the equivalent to an upgrade! It should take about 15 - 20 minutes (more or less);
1.3.) After installing Snow Leopard, you're Mac will restart.
1.4.) Once you're Mac boots again, update it, to make sure you'll have the 10.6.8 update installed! (The final update!)
1.5.) Now connect you're Time Machine!
1.6.) Insert the Snow Leopard DVD once again and wait until it's window to open; Click on the installation icon once again;
1.7. Instead of installing it again, simply click on the button "Utilities" (bottom left of that window!);
1.8.) Choose to restore a backup from Time Machine and follow the on-screen instructions (that will end with a restart of you're Mac).
1.9.) After the restart don't click on any key! Just follow any instruction the computer may give you: this part is by far the easiest.
IF, this doesn't work:
2) You could boot from you're Mac without the Time Machine.
2.1. Once you enter the Desktop, connect you're Time Machine;
2.2. If possible, perform the installation and then, access it contents!
2.3. Copy any data you'd like an paste it on the correspondent folders (eg.: copy you're photos folder a paste it on the same location where it once was!);
IF, this doesn't work:
3) Connect you're Time Machine to another Mac and try to perform a copy of all it data to the Mac where you connected you're Time Machine.
NOTE: To avoid over-righting any data that the Mac as, create a partition using "Disk Utility". The restore you're data to that partition!
To tell you the truth (and I hate to admit this), I'm actually running out of options. I'm pretty sure you did everything ok (erasing you're HDD and installing the OS X)… if the compatibility issue prevails you should contact any technical assistance. Usually they can restore Time Machine backups into external HDD (or into the HDD of you're Mac if you allow it). It not the "free" king of help, I know!…
Let me know if my suggestions solved you're problem.
If you need my help, please, don't hesitate to contact me.