I had a similar problem with a new laptop my sister asked me to install Vista on.
It was my first go at Vista and it nearly drove me mad, dunno if this will work or even why it worked, but here goes.
Log into your router and and make sure UPNP is switched on, I think I actually disabled it, rebooted the router and enabled it agin just to make sure.
Switch off and unplug router and modem, power down PC, leave it a few mins.
Plug in modem, let it boot up, connect to router.
Plug in router, let it boot up, boot up PC.
Also, cos I aint convinced the above is gonna help ya, I'd try disabling the router's firewall and make it public, security off, so anyone can connect and try again. That way you can rule out bad config as far as security goes.
Lastly, have you checked for new firmware for your router..?