Ok.
I'd suggest only connecting through ethernet for starters, run a 'test connection' on your 360 to establish NAT, DNS setting etc.....
You'll also need to amend some settings on your router, firewall might cause some issues so can always be disabled. You really want to be able to set the router so it automatically assigns an IP address when you boot up your 360. Lastly, on your router check for an option to enable UPNP, this is specific for gaming so allows for freer moving traffic between your 360, the live servers, and other 360s you want to hook up to. Hope this helps........if not, try googling - 'virgin media xbox live issues' and you might have more luck. Hope you get it sorted mate, i know how maddening it is not being able to get on LIVE and kick some a**!