I'm getting the same message, and I'm pretty sure I know why I'm getting it. However, I don't have a solution yet. I had a home network coming from a time capsule, and I wanted to add an airport express. I managed to make it work, but had to reset the time capsule in the process. I used Airport Utility 5.6. After this, when I entered time machine in system preferences, it said that the computer had never been backed up, and when I tried to start a new backup, it gave me the error that we all have. I figure that the addition of the airport express caused the computer not to recognize the network as the same one the time machine is on, and thus cannot connect properly. That's what it sounded like, anyway, based on the result of me trying to verify the backups (menu bar icon + option). I'll try messing around with it in airport utility, and i'll let you know if I figure anything out.