Hey there, Austin Powers, are you having trouble getting your Time Machine to be-have? Two Apple tech notes spotted by Macfixit.com point up a pair of issues that may prevent your backup mojo from working.
First, if Time Machine backs up about 10 gigabytes and then stalls out, you probably need to reformat your target drive with either GUID or APM partitioning (depending on whether you're backing up an Intel or a PPC machine; no word on what to do if you plan to back up a mixed environment to the same drive). Second, if your backup files don't show up in the Space: 1999 interface, chances are you've got non-alphanumeric characters in your computer name, and you'll have to change that before TM will work properly. If you've upgraded your computer, you need to give the new machine the same name as the old one.
It's not yet clear why the machine name is crucial to proper TM functionality -- perhaps the path names need to be "UNIX legal" to work with TM's linking scheme? In any case, try these two tips if your Time Machine is trapped in feudal Japan.