to 3.1.2, keeping the phone jailbroken. I believe the Vodafone UK settings are live on iTunes now, so it shouldn't need to be unlocked now? Its a 16GB 3G BTW.

Having the settings on iTunes is irrelevant, if your phone is locked to another carrier then changing the settings just mean it wont work.
If it is an O2 phone then they will unlock it (£15 if PAYG) otherwise your best bet is to use Pwnage to upgrade, preserving your BB so you can still use UltraSn0w.