Leopard Backup downgrades Snow Leopard installation upon recovery
The best way to avoid this is to do an upgrade from Leopard to Snow Leopard rather than an erase and install. Snow Leopard shouldn't give you the option to erase and install, it should automatically upgrade. Are you erasing your hard drive before installing Snow Leopard?
By default, Time Machine backups retain all system software, including your OS. If you want to disable this, try this:

Open System Preferences
Click on the Time Machine Preference pane
Click on Options...
Click the + button
Navigate to /System
When you get the following message, click &quot;Exclude All System Files&quot;


In the future, this will prevent Time Machine from backing up system data, but it will still back up your personal data and applications.
For your current predicament, you'll need to do a standard install of Snow Leopard instead of erasing the hard drive first.
Good luck.