I've used any number of machines to connect to that. Sometimes I find I have to disable the wep/wpa security first and then it connects. Next we explore what security we can use. Also I have my wifi router set to only allow certain machines. All this is far from automatic.
But the first test would be to connect to some hotspot to see your new laptop is OK.
Bob
I recently purchased the brand new IMAC Core with the pentium processor. My wireless router is working with all the other computers in the house, includuing a laptop G4 with an Airport card. My new IMAC is recognizing my network which is listed under the airport button on the top of the screen. When I select the network I get a message that says Airport cannot connect to this network. Apple doesn't know what the problem is nor does Verizon. I can connect to the internet via ethernet from the same router. Any suggestions, I'm about to return this computer.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic