Astounding. Thankfully I have a little netbook at home I use as a web server, and it is running some variant of ubuntu. I recently moved my Mac Mini to my office (I hated my windows machine so just unilaterally brought in my Mac). When I did, I brought in this old 150 gig external hard drive I had kicking around. I had barely used it for years, but did occasionally and it always worked properly.
Once I got everything set up at work (which was about a 10 minute job, by the way, from plug in to figuring out all the networking stuff--super easy), I tried to back up to the drive. It went sideways, but I have lots of experience with Time Machine doing that. I did all the regular things in terms of deleting the .inprogress file, reformatting and even repartitioning the drive. I tried Disk Utility and formatting from the terminal. Things just got worse and worse, with more and different errors.
Weeks passed. (I wasn't working on this full time, of course, since I do have a job and the backup was entirely unnecessary at work, since I have the windows box sitting on the floor should I really need it.) I saw the post below. I said, what can it hurt? I took the drive home, plugged it in, and linux said it couldn't format it because it was in use. So I ejected it from the linux desktop and tried again and it said "fine." It was that easy. I spent a week with Disk Utility on my Mac trying to format or partition it, with errors most of the time, or at least a drive that failed on backup if the partitioning or formatting worked. Linux just partitioned it and that was that.
Note, though, that Linux -- at least my distro -- can't format as HFS+ or any other Mac file system, so I just partitioned it and left the partition unformatted. I then plugged it into my Mac Mini at home (which is not the same machine as my Mac Mini at work -- I bought a new one for home when I took my old one to work) and was able to see it in Disk Utility so I added a Mac OS X journaled partition. This time, finally, it worked.
I came to work, plugged the drive in, told Mac OS X to use it for Time Machine, but to exclude the external drive from spotlight, let it go and bam, everything worked fine. I finally have backups again.
Man, Time Machine is nice when it works, but it has been a nightmare for me after upgrading to Lion (which I run at work and home). I have had to get dirty with terminal and delete .inprogress folders many times, and then all the above craziness happened. Something has gotten very broken in this latest iteration of Mac OS X I think.
Anyway, thankfully, the LAST error that I was having with this drive in Mac OS X was the "Unable to write to the last block of the drive" error. That was only after I switched to a USB cable. (Before that I had been using the firewire interface on the drive, with different errors every time I tried to back up, partition or reformat. Shrug.) It's a good thing I had that error and found this thread.
I just had the same problem with an external USB disk that I tried to repartition. No matter what I did (using diskutil and dd in the Terminal, ...) I couldn't get rid of the error.
But then I plugged it into a Linux box and partitioned it there without any problems.
When I plugged the disk back into the Mac, I could format the linux-created partition with Journaled HFS+. Problem solved!