I would try this first:
Format that external again as Mac OS Extended(journaled) and try again with the backup.
Alternatively, the purchase of another external drive, USB 2.0 is cheaper than Firewire, might be an option if you don't like the idea of an Archive and install
White MacBook (about 4 months old) OSX 10.5.8, Using 115GB Iomega HDD (3x size of MacBookHD I'm backing up), tried diff. FireWire cables.
Shortly after purchase T.M. began giving a warning after 12-18 days that it hadn't backup up for that time. I ran Disk Warrior on both the internal and external drives. Run Permissions regularly. The Iomega works perfectly with T.M. on my old iMac and vice versa.
In T.M. Prefs it always says "Last Backup: Failed" and "Backing Up: 30.3MB of 30.6GB." It's been stuck at that for a week now! Yet the T.M.arrow-circle in the menu continues to revolve. Lately I get a mysterious warning: "The application PubSubAgent quite unexpectedly." Don't know if that's related. Otherwise no problems at all with MacBook, so I can't image doing an archive & re-install as AppleCare has advised! Also getting no help from other forums or Just Answers. Any ideas out there?