I recently started getting this error message in Time Machine:
Unable to complete backup. An error occurred while creating the backup directory.
My configuration: Unibody Macbook Pro 15" (circa September 2008) & Western Digital Passport 500GB (USB HDD), OS X 10.5.7 (up-to-date).
I couldn't get rid of this problem through unplugging/replugging my external HDD, and eventually rebooted the machine. The problem is gone for the time being but I'd like to find a better solution than "reboot and pray".