Just to add my own experiences to Nick's post, in the hope that it might help the fog clear for those of us who are currently struggling with this :
I have an Airport Extreme (c2008) running 802.11g/n which is the wireless access point for my mid-2008 MBP, iPhone 4, and iPad, all of which have been running perfectly well straight from the box. At no point have I ever had any networking issues and the setup of every device has been really easy to do...
...until last week when I bought a late 2010 13" MBA (2.13Ghz), which is really struggling to make or maintain any sort of connection with the internet. The symptoms are exactly the same experienced by others in the thread(s) on this forum - connection fine one minute, no connection the next, successful connection to the Airport Extreme and Network, but no connection to the ISP and Server. With Wi-Fi off, ethernet takes a little time to sort itself out but then works like a dream.
I've checked settings across all devices and they appear perfect - the common settings you would expect to be the same
are the same; each unique device has its own unique IP address; all are using WPA2 security; there are no issues with subnet masking and each device is even recognised and accepted by my ISP router (an ethernet based BT Home Hub 1.5). Refreshing the DHCP lease for the Wi-Fi connections has no impact.
I've run the hardware test on my MBA and - as you'd expect - its 100% functional. I've even checked the RSSI levels for every device and they're spot on - each device is receiving the same signal strength.
So, every other device on my network is fine. Given that 99% of the settings are the same across all of these devices (unique IP addresses and MAC address being the obvious exception), and that my MBA is the only device which has a problem, I'm of the same opinion as Nick - it absolutely must be the MBA which is the heart of the problem.
Sorry I can't offer a solution, but I hope that my contribution might help in some small way - in the meantime if I manage to learn any more I'll naturally post my findings here.