I would try:
- Turning off wifi (Settings >> Wireless & Networks | Wifi)
- Turning mobile data on (Settings >> Wireless & Networks >> More >>
Mobile Networks >> Tick "Data Enabled")
- Toggling airplane mode on few a few seconds (Settings >> Wireless & Networks >> More >> Tick/untick "Airplane Mode")
Then you should see E, G, 3G or H appear over your signal bar (the cellular reception one, not the wifi one) and you'll have internet access.
If that doesn't work, then please go to Settings >> Wireless & Networks >> More >> Access Point Names and make sure you have a listing for 'Orange UK'.
If you click on Orange UK, the details inside should be as follows:
Name: Orange UK
APN: orangeinternet
MCC: 234
MNC: 33
APN Type: default,supl
All other fields should read 'Not set'.
If you have to alter any of the details under Access Point Names, you should then go and repeat the first list of steps afterwards.
Lets not jump too far ahead of ourselves.

It is likely unrelated to the VZW problems as that is CDMA and AFAIK they don't use that across the pond.
Yeah, it's GSM only here.