Found this information useful so I'm passing it along: The bad news is, we have discovered a Leopard-related issue that may very well throw a monkey wrench into your Time Machine. Anyone trying to use Time Machine with a previously PC-formatted drive could be at risk. The good news is, there is an easyalbeit none-too-obviousfix. Here's the dilly-o: After I upgraded my MacBook Pro to OS X Leopard, the first thing I did was grab a brand-new Maxtor USB drive and format it to Mac OS Extended (Journaled) using Disk Utility, just like I had countless times before. As soon as I erased the disk, Time Machine popped up as promised, and asked if it could use the disk for backup. I said yes, and was on my merry way. Only I wasn't. Time Machine ran for a bit, and then crapped out after about 10GB. I went into Disk Utility and saw that although the partition was formatted Mac OS Extended (Journaled), the volume itself still said FAT32. I clicked Erase to reformat the drive, and got the format failure error you see above. I tried this with FAT-formatted drives from Seagate, Iomega and HP as well. Each time I saw the same thing. I could reformat the partition to Mac OS Extended (Journaled), and Time Machine would recognize it. Get Info would say that it was formatted correctly. But Disk Utility showed that the volume was formatted for PC. Inevitably, if the Time Machine backup was greater than 10GB, there were problems. Worst of all, if I dared try to format the volume for Mac, I would get the dreaded error, and the disk would be temporarily unmountable. Not only did I vary drives, but I tested the problem on various systems too. I tried it booting from the Leopard DVD, with the same results. Ditto when I tried it using my wife's Leopard-upgraded MacBook Pro. (Yes, his n' hers MBPs. You can insert your "awwww" here.) The end result was that I couldn't break the FAT grip on these damn drives. I made some calls, I talked to some people, and eventually here was the solution: you wipe the hell out of the drive by creating new and different partitions. So, do not head to the Erase tab in Disk Utility to prep a PC-formatted drive for Time Machine. Instead: Go to the Partition tab. Create two partitions. Under Options, select GUID Partition Table (what you would use to make a Mac OS boot disk) and click OK then Apply. Once your partitions are in place, do it again, reverting back to just one partition, but still keeping the GUID Partition Table option. Click OK and Apply again, and at this point you should be cool. To be safe, you can then go to Erase and set formatting for Mac OS Extended (Journaled), then format it once and for all. But when you get there, you will probably see that your volume is already formatted in the right way. UPDATE: Some people have gotten this to work without creating two partitions. If you like, try creating just a single partition, but using the GUID Partition Table option. This may be all it takes to break the chokehold. Using this method, I have gotten all of the disks to work just fine with Time Machine, and I don't anticipate any problems in the future. OK, I know, quite a bit of nerdiness, but I wanted to get out there and tell you about the problem I encountered, in case you are having the same troubles, or plan on getting there sooner or later. Also, this solution is actually a workaround of sorts. My hope is that Apple can update Disk Utility with a stronger form of disk erasing that doesn't require so many manual steps, but if I am missing something obvious, I'd love to hear it. Please share any troubles you've had, or any better solutions you've cooked up. Special thanks to Dorian and Ken!