Interesting result, particularly if it turns out that they sent you one of the new models of the router. I was aware of problems with the new Intel machines and wireless networking but was under the impression that this particular bug was fixed in an update to the Airport software around Christmas. This I remember distinctly since I had been unable to connect my new MacBook Pro to the wireless network of a hotel that we were staying at (well, it could connect to the network but was not receiving a valid IP address) but after the release of the update I could connect to non-Apple routers without trouble.
Still, free is free and you can't argue with that so I hope that this sorts everything out for you.