Getting some really annoying network issues with my Bold.

Using it on the O2 network, it says O2 on the home screen, and getting full signal strength. Can't make any calls. Services Status tells me

Mobile Voice
Status: not available
Connection: not connected

If I put a Vodafone sim in I get decent signal, but phone calls/txts etc work and I get Status: available.

Why does it do this happen on the only network I actually want to use?

Any ideas would be greatly appreciated.

Cheers,
Jack.