Click on your hard drive in the finder and do a Get Info (command i). Is the format Mac OS Extended (Journaled)? If it isn't the formatting didn't work. Try it again following the directions in
this article. People with PPC Macs should substitute Apple Partition Map for GUID when following the directions.
If the formatting is correct launch Disk Utility which is in your Applications > Utilities folder. Verify your internal disk and Repair your Time Machine disk. If there are any errors reported for your Time Machine disk repeat the repair process until no errors are reported
If your internal disk shows any errors boot from the Leopard install DVD. Hold down the "C" key immediately after the startup chime and keep holding it down until you see the spinning gear. Pick a language and choose Disk from the Utilities menu. Repair your internal disk and repeat until no errors are reported. Then Repair Permissions.
If that doesn't work launch Console which is in Applications > Utilities. Choose All Messages in the left pane of Console and type in "backupd" without the quotes in the search window to see the Time Machine log. Post any errors you find.