Your SIM may be flaky. Try replacing it if possible. I am saying this based on my experience ,read on if u care.

Sharing my mom's experience(or I guess mine since I'm her technical support and I get daily calls) with a SIM and Nokia 5230 + Samsung Gravity 2.

She was using a refurbished Samsung Gravity 2 that did not behave very nicely so she wanted a new phone. Bought the 5230 put in her SIM and it would give her a "Connection Error" every time she called somebody, most of the times before the 1 min mark. The same SIM worked like a charm in the Samsung. After random testing etc I realize that the SIM card is to blame even if it worked fine in the N900 and in Samsung.

I was able to get her a new SIM for free and I haven't received a call regarding her cell since then. It's safe to assume it's working well.