The "preparing" stage in Time Machine is usually fast, because Time Machine uses a log of file system activities to know where to find changes that need to be backed up.
But there are things you can do to make that log untrustworthy. When Time Machine discovers the log MIGHT not be valid, it does a full scan of your file system to determine what really needs to be backed up. This can take a while. On my Powerbook (and with a firewire external Time Machine drive) it can result in a "preparing" stage that lasts 20 minutes. If you let Time Machine continue, it will eventually figure out what really needs to be added to the backup disk and will continue. This, of course, is better than just gambling the log is correct or just backing up EVERYTHING again even though only a few files might actually have changed (which would take much longer and consume more Time Machine disk space).
In these early days of Leopard installs, one of the most common things you can do that will make the log untrustworthy is booting from the Leopard install DVD. Each time you do that, the next time Time Machine runs it will discover that your hard drive MIGHT have been modified without the changes being reflected in the log. So it does the full scan -- a long "preparing" stage -- to insure it gets things right.
