It's nothing to do with Virgin.
Make sure that UPnP is enabled on the router.
You may need to manually give the 360 a static IP address, & then forward the relevant Xbox Live ports to it using the router's admin interface.
http://support.microsoft.com/kb/908874
http://portforward.com/english/route...x_Live_360.htm