tl:dr
If you have lost Virgin Mobile data connection but have a 3g symbol still join a wifi network and go to m.apnchanger.org then select Automatic. Find UK - Virgin and accept the profile.
Long story
My mobile network is Virgin Media in the UK and yesterday the data stopped working on my iPhone. Wifi was ok but not mobile data. The 3G symbol was showing so the network 3g was ok, I just couldn't connect to it. Occasionally I'd get a message telling me I wasn't subscribed to a cellular network. Of the many things I tried to fix it were turning cellular data on and off, turning 3g on and off, turning the phone on and off, removing and replacing the sim card, resetting the network settings (from Settings, General, Reset) all of which got me nowhere.
After having fun doing that I decided to look for a status page on Virgin's website, but there doesn't seem to be one. Checking the forum I found this thread about no mobile data connection which wasn't very helpful as it mentions on how to fix it if using an Android phone. So I go to search for how to change APN settings on an iPhone to discover that the mobile network decides if you can access these settings. So it's not possible to fix a change by Virgin Mobile as they don't allow access to the options needed. Argh! Thankfully I discovered the apnchanger.com website. I hopped on wifi and opened my browser to m.apnchanger.org and found the Virgin UK apn profile and installed it. Bingo! Now it is working. No thanks to the Virgin techs.