I own a blackberry bold 9780 and over the past few weeks my phone will say SIM not allowed at random times, I have to re-boot my phone and take the sim out for a minute in order for it to work again.
Also I have noticed text messages aren't sending as quick as they usually go, sometimes I get a message saying network congestion and have to re-send the text.
I've checked the status checker and it says service should be good for my area,although there is going to be maintenece work on the 10th (does this mean my service will go down?)
It sounds like a firmware or hardware fault.
First off check which firmware you're currently running (Options > About > Written on third line). If that's pretty out of date then update that.
If the firmware doesn't help, it would be looking at the phone, if you can beg or borrow another Blackberry and try your sim in that, that will help identify if it's a network or handset fault.
Is the handset still under warrenty do you know?