Have you previously connected the Laptop to the Router?
If so, go into the Properties of the "wireless network" and make sure the option to connect even if the router isn't broadcasting its SSID has been enabled. This should get around the problem of the adapter not finding the network, even if it is actually broadcasting.
What router have you got? I've just installed my first wireless router, and it comes with its own setup program which makes setting up a doddle -- if you understand what all the terms mean.
With mine (a Netgear) among other things you can do in the setup program is set wireless on or off, and set different levels of security. Part of the security is that you can set it so that it won't let anything connect wirelessly unless they've been given specific access permission.
Did you run the setup program from the Virgin CD? If my setup was anything to go by, you run the CD before you plug in or power-up the router, and then the setup program will tell you what to do step by step.