Got a call from someone who thought I could help them on this, but I personally know nothing about it. The phone was bought in Mozambique and it can't be used here on our SA networks (from what I gathered on Google). Is it even possible to get around this issue on this particular phone?
(I probably should have used the search first...)
I'm having the exact same issue with my girlfriends iPhone that her brother gave her. The phone is locked to Vodaphone Australia but because it was a warranty replacement, it doesn't seem to be in Vodaphone's system.
I've gone the whole jailbreaking route and to be honest, if you can avoid it stay away... Jailbreaking any phone from the 3GS (new boot rom) and up is a nightmare, especially when it comes to the latest iOS versions.
I honestly dont know wtf is wrong with people that still jaibreak, they must be sadomasochists. If you can, try to contact the network which it is locked to and have them do a network unlock.
If not, do a lot of research before you jailbreak.
Some tips:
Make sure that you have SSHH blobs for whatever OS version you wanna jailbreak to (stay away from iOS 6 as it cannot be untethered and its difficult to downgrade to iOS 5).
Make sure that the iOS version you want to to jailbreak can be untethered and that it can indeed be hacktivated (network unlocked).
Good luck.