A while ago I set-up my Airport Extreme router with my Virgin Media cable connection and it was painful, but I got it working. Anyway, a friend had similar trouble so I helped him set up his and given that this might be a relatively frequent occurance and Virgin's support for Apple products equates to zero I thought I would post the info here for others to benefit.
Step 1) Plug in the relevant cables
I'm not going to go into detail here, but basically plug the ethernet cable into the "Ethernet" slot of the set-top box then the other end into the router in the slot with the circle of dots around it. Make sure the set-top box is powered on and the router is too.
Step 2) Install Airport Extreme Software Update
Chuck in the Apple provided CD and run the installer, then reboot.
Step 3) Enable Wireless and Connect to the Base Station
Enable your wireless connection and then connect to the Wireless network. It is probably called "Apple Base Station" or some generic default name.
Step 4) Run "Airport Utility"
Run the "Airport Utility" program in "/Applications/Utilities/Airport Utility". Then it should automatically discover your base station. Click on the base station and then click the "Continue" button in the bottom right. When prompted choose "Assist me".
Note: Do not confuse it with "Airport Admin Utility" this is the older software.
Step 5) Network/Base Station Name
Select an appropriate network and base station name. Anything you like really.
Step 6) Country/Radio Mode
Choose your country (ie United Kingdom for Virgin Media) then set the Radio Mode. If you have any already Macs or PCs you may need to be 802.11a compatible.
Step 7) Security
Set-up security, don't choose WEP as it is known to be insecure. Select WPA2 Personal and enter an appropriate password of your choice (make sure to check the "Remember password in Keychain option")
Step 8) How do you connect to the Internet?
Select "I use a DSL or cable model with a static IP address or DHCP" then continue
Step 9) Internet Setup
Now the fun begins. If it weren't that Virgin Media's customer service people were so incompetent this bit might not be such a pain, but in my experience they gave wildly different numbers for the primary and secondary DNS depending on who you spoke to. Anyway, enter the information as per the below:
DNS Server: 22.214.171.124
Domain Name: ntlworld
DHCP Client ID: (Your Virgin Media PID - phone them if you don't know what this is)
Some Virgin Media reps stated you could leave the DHCP Client ID blank, but in my experience this didn't work when setting up both mine and my friends. Once you're done click "Continue"
Step 10) Enter a base station password
Make sure you enter a "base station" password and then once you're done click the "Update" button.
At this point your Apple router will reboot, but it is likely it will flash an Orange light and give several error messages relating to different things. So go back to "Airport Utility" and click on the router again and the "Continue". Now instead of "Assist Me" select "Manual Setup".
Step 11) Share a public IP address
The router is probably set-up in bridge mode. This is problematic as it means you have to do the whole "NTL provisioning" thing for each machine in the house, a pain. So instead in the "Manual Setup" screen of "Airport Utility" select the "Internet" tab.
Now at the "Connection Sharing" bit under the "Internet Connection" tab change the "Off (Bridge Mode)" setting to "Share a public IP address".
You may also want to click on the "DHCP" tab at the top and change the lease time to a bit longer if you want to have the same IP for longer.
Also in DNS Server(s) it only has a primary DNS server, enter "126.96.36.199" as the secondary DNS (in the second DNS Server field).
Once you're done click the "Update" button again and wait for the router to reboot.
Step 12) Diagnosing problems
If the router is still flashing orange go back into the "Manual Setup" bit and in the "Summary" screen click on the Orange icon next to the "Base Station Status" field.
If you get the "Double NAT" problem ignore this for the moment as it is only because the router has been assigned the temporary provisioning IP address from Virgin.
If however you have a "Internet Connection" problem, then unplug both the set-top box and the router then restart the set-top box wait for the lights on it to stop flashing then turn on the router. Once they've both rebooted you will probably still have a flashing orange light, but it should be related only to the "Double NAT" problem mentioned earlier
If you go back into "Manual Setup" of your router and look at the "IP Address" field in of the "Summary" page your router should have an IP Address that starts 10.* etc. This is the private network of the Virgin provisioning system.
Step 13) Provisioning
If the router is only saying it has a "Double NAT" problem and it has successfuly obtained an IP address starting 10.* and not 168.* then you are ready to start the provisioning step.
Open up a browser and go to some common site like google. You will get redirected to a "NTL Provisioning" site that has a big "Start" button on it. Go through the steps. You will need your Virgin PID and password handy. If is not getting as far as the NTL Provisioning screen then try to quit the browser and start it up again then try again.
If this STILL doesn't work then phone up Virgin by dialing 150 on your phone and ask them what the IP address of the NTL Provisioning site is (when we did it started with 173.* but this might change) and then enter the IP into your address bar.
Once you have successfully registered the router with the "NTL Provisioning" system restart the router (turn it off at the wall and on again)
When phoning Virgin Media don't mention the words "Apple", "Mac" or "Wireless". They will use any excuse to say they don't support it. Just saying you're setting up a generic router, and need help and they're more open. If they ask the make of the router, fabricate something like a "Belkin router". As I said they're just keen to get you off their backs than anything. Good luck!