See the info here.
Open the airport extreme and look at the logs.. see if the wireless has experienced dropouts..
Although the problem is not Lion/wireless/7.6.1 combo per sec.. that is not infrequent result. The backup can end up corrupted and fails the checks.
Is the other computer without issues SL not Lion?
Or uses ethernet not wireless.
If you cannot connect by ethernet to the computer that has trouble, try setting the AEBS to manual wireless settings.
Change all names .. ie the AEBS itself and the wireless name (SSID to everyone but apple) to a short name, no spaces no special characters, ie pure alphanumeric. Different name also no spaces for 5ghz.
Change wireless mode to a/n-b/g manual.
Change channel to manual.
Test using channels 1, 6, 11.