First, I must say if you are running Lion you shouldn't worry about this, as all Lion machines have a "Restore Partition". That is they save all the system files required to restore the system on a special "section" of the disk unaccessible under normal conditions. If you ever do want to access this Restore Disk, simply hold down the option key while your Mac is booting up, and you should see be able to select it.
Time Machine, as far as I can tell, DOES backup system files. It full copy of your drive. Nonetheless, time machine backups are not bootable. You can save space by excluding system files, or any other big files you might not want/need to back up. Here are some articles that might help you with that: Time Machine tips and troubleshooting, Guide To Excluding Data from Time Machine Backups.
If you don't, time machine will leave them, no matter how old the data gets, and it would display an error/warning if you run out of space rather than deleting them. Time machine makes sure to always have at least a single full copy of your system.
Regarding space, you can backup a larger drive with a smaller one, as long as your Time Machine Drive can hold all the space you are using on your larger drive. So if you have 800GB in your system, but have only used 200GB, you could back it up with a 500GB drive, though it is not recommended, because if one day you do fill the drive Time Machine wouldn't be able to have a single full backup. Nonetheless, if you keep your actual disk usage below your Time Machine Disk capacity, you should be fine, with at least one full backup.
My final recommendation is you check those articles and save space for your backup, excluding the system files (Time Machine backups aren't bootable anyways. You'd need an installation disk or a Recovery Drive.) and any other large, unimportant files. Finally, keep an eye on your backup, and if you find out you do need more space I really recommend buying a larger hard drive! Time Machine can come up pretty handy in times of despair!
I manually changed the permissions and now all is well. I can once again see the old backup and restore. Used the following commands.
cd /Volumes/TM/backups.backupdb
chmod -N hd
chown root:wheel hd
chown +a 'group:everyone deny add_file,delete,add_subdirectory,delete_child,writeattr,writeextattr,chown' hd
tmutil associatedisk -a /Volumes/TM /Volumes/TM/Backups.backupdb/hd/2012-11-08-145609
Best Answer
The permissions fix is to Open Disk Utility, select your boot disk and run the Repair Disk Permissions
What this does is compare the permissions of the files and directories installed by Apple to what is expected and changes them if needed.
If you have just installed OSX and then installed from a good backup then all the files will have the correct permissions and will not change anything. So it is a step that is a double check and probably not required but might find something on odd occasions. I would not run this as if there was a difference between expected and actual permissions I would want to know what it is and work out what action broke the set up and fix that error and fix that action.