Funny thing is that the dialog has an OK button. It's really not OK. Why not? Because it didn't tell me where the problem was.
As I've said before, I love the simplicity of Time Machine, though presenting an error message like this is not very helpful. Something - anything - to indicate what went wrong would be a good idea. I accept that you don't want to scare off the non-techies with a detailed error message but having a little "more" link that described what the problem is would have helped.
Rather than investigate I decided to go with the flow. I clicked the OK button and then told Time Machine to back up now. It happily whirred away and looked like everything was fine, then at the very end up popped the failure notification again. Crap.
I did what I always do when something unexpected happens on my computer: I Google'd up the error message. There were a number of solutions offered up, many involving reformatting the TM drive. I felt that was a little drastic so I looked into the Backup drive in Finder and saw that the last folder was:
I dragged that folder into the Trash can and was prompted for my login credentials. The file was whisked away and I asked Time Machine to do another backup and it proceeded fine.
Finding out what happened
Wanting to understand why this occurred I popped around looking for logs. In reviewing the current System Log (/var/log/system.log) I found entries that indicated one of my Growl plugins had a problem being written to the backup. Once that occurred the "in progress" backup file was corrupted and needed to be deleted in order for Time Machine to continue.
I'm not sure what caused the problem. The backup and main disks appear to be operating fine; I ran Disk Utility's Verify Disk on both and they came up clean. Perhaps a Growl notification opened the plugin in mid-read? Not too sure but it all seems fine now.
If you happen to get the error message above you may want to just check your backup volumes to see if you've got an open backup that's listed as In Progress, even though Time Machine is not running. Try deleting that to see if it allows your backups to continue. At least that's what worked for me!