I had this problem with on Orange UK on my Nokia e61!!!
i called them up and they fixed it for me, basically they told me to take out my battery and put my sim in another Phone and call voice mail or something, cant quite remember.
Phone them and ask them