Does the same thing happen with your sim in another phone?

Or someone else's sim in your phone?

I had the same trouble (Crazy John's); it was my sim, they gave me a new sim = no more trouble (a micro sim vs a cut "normal" sim)