Our true genius died a little while ago.
But up to Mountain Lion he has tones of info ..
http://pondini.org/TM/Troubleshooting.html
Try some of the section C solutions.
It is more than likely network.
BUT do the following.
1. Install the widget A1
2. Reset TM, A4
3. Verify the backup, A5
4. Reboot the whole network and restart it in order.. modem.. TC.. MB Air.
No luck to this point.
Tell us exactly what OS you have.
The worst possible is Mavericks. If you are trying to connect to old backups after an upgrade it is hopeless.
I recommend you start over.
Simply wipe the TC and start afresh.
Manually mount the TC disk in Mavericks so you are sure it is working. Tell us if you run into trouble.
Most important.. in wireless network preferences are you running ipv6 in link-local mode.