I have had a similar problem with Time Capsule, Time Machine and Mac OS 10.7.
In french, Time Machine was telling "Recherche du Disque de Sauvegarde" which seems to be similar to "Looking for Backup Disk" and couldn't backup anything.
I've resolved it (while keeping the last backup) with following what is described there :
https://discussions.apple.com/thread/3638823
Below, what I have done in details :
To your own risks... (risk of erasing everything on the mac and of deactivate some functions... and to be unable to recover anything)
It has worked for me but it couldn't for you.
1/ Deactivate Wifi on the Mac
2/ disabled the backup from the preferences panel
No pending backup.
Open "Terminal" app
3/ disabled spootlight:
sudo launchctl unload -w /System/Library/LaunchDaemons/com.apple.metadata.mds.plist
(described here : http://osxdaily.com/2011/12/10/disab...mac-os-x-lion/)
4/ delete the following hidden folders from the diskboot and external drive backup (.Fseventsd and. Spootlight-V100)
4.1/ delete .Fseventsd on the mac, enter :
cd /
ls -l
(you must find .fseventsd and .spotlight-vt100)
sudo rm .fseventsd/fseventsd-uuid
sudo rmdir .fseventsd
4.2/delete spotlight-vt100 of mac :
sudo rm -dR .Spotlight-V100
4.3/ delete .fseventsd of Timecapsule :
cd /Volumes
ls -l (you have to look for the backup directory)
cd Cop* (because for my computer : the name is 'Copies de sauvegardes de Time machine' and it is the single directory name begining by Cop)
sudo ls -l (check presence of .fseventsd et Spotlight-vt100)
sudo rm -dR .fseventsd
4.4/ delete .spotlight-vt100 :
sudo rm -dR .Spotlight-V100
5/ Restart Time Capsule and mac
6/ spootlight rehabilitated (details here :http://osxdaily.com/2011/12/10/disab...mac-os-x-lion/) :
sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.metadata.mds.plist
and index launch (found here : http://www.printedbyerik.com/2011/08...index-on-os-x/) :
sudo mdutil -i on /
It took 4 hours for 500Go
7/ at the end : put an internet cable between Mac and Time Capsule (it is mandatory)
Launch a backup in Time Machine preferences.
For my computer : 15 hours for 70Go.
3 backup since without any problem.