I am running a Vodafone Nokia N95 on Vodafone On Account

For a while now, just about every time I try and make a phone call it will take ages to connect then a Msg will pop up on the screen saying "Connection Error"

I have to try to call again 3 times before the call will go through.

I am also getting Missed calls, when my Phone has been on loud sitting right beside me. It just never rings.
I also send a txt msg and it will not send it will just sit in my outbox until I resend it..

At the start I thought it was just a coverage issue but this is happening at work & home I work/live in central CHCH

Any ideas of what could be causing this?

I called Voda and they said to try out my sim in another phone, but it's not happening constanly so I would have to swap a few days etc. to see if it was happening and I do not have access to do that.

Any help would really be appreciated.