I had similar Problems with my Time Machine Backup and wanted to share my solution too, maybe it'll help somebody here.
This solution worked on a Macbook Pro Late 2011 with OS X 10.8.2 Mountain Lion and an external HardDrive connected via USB (so no Time Capsule involved in this case!)
I copied the "com.apple.TimeMachine.Plist" and the "com.apple.TimeMachine.Plist.lockfile" (can be found in /Library/Preferences/) to the Desktop and then deleted both files in the Preferences Folder.
Then I disconnected the HardDrive and turned off Time Machine. Then turned Time Machine back on and plugged the HardDrive back in again. (A new "com.apple.TimeMachine.Plist"-File appeared in the Preference Folder, I deleted that, too.)
Then I started the Backup and it said looking for Backup Disk again, another new "com.apple.TimeMachine.Plist"- File appeared and while Time Machine was searching for the Backup Disk I deleted the File and Time Machine immediately found the Backup Disk and started the Backup process. (Which again created a new "com.apple.TimeMachine.Plist" - File...)
But now it works perfectly again!
Only thing I don't know now is: What should I do with the lockfile I copied to the Desktop? Does anyone know what that file is good for? Do I need to copy it back to the Preferences Folder?