Hey there guys, thanks for the replies so far, glad to hear others are experiencing this annoying problem. I seem to have had this since rooting it, originally T-Mobile though I am 99% it was never "locked" to the network for some reason as I mentioned as I have never had to enter the 00000000 code, which the free ChainFire sim app gave me (seems like it means it is unlocked already???). The guys on the 3 helpline were giving me loads of codes which weren't of any help, and telling me about what options I could fiddle around with, but I had tried all of these to no avail.
Are people also getting the MMI message I mentioned in my original post, whenever they enter # codes in the dialer? It seems to me that both of these problems started at the same time (this error message and the forwarding issue - I am sure they are linked). It means, for example, I probably won't be able to set up a speed dial because of it, nor will I be able to use the "secret codes" as mentioned in the dedicated thread of the same name on this site.
Why is it a problem for some and not for the majority of people, we must have something in common which we have done with our phones which has caused this?
I really hope someone can sort this annoying problem out.