"Invalid Sim card" problem(non blooked phone)

first, unless im really bad at looking for solutions in google, there is nothing i could find to solve this so i decide to post it..

i have Blackberry bold 9700 - v5.0.0.680 (bundle 1149, platform 5.1.0.160)
ive been using it for about 4 months now was working great in few diffrent countries such as canada, the us, israel and even ukraine..
currently im staying in ukraine.. came here about 3 weeks ago, when i first came i just bought a noraml simcard from MTS UKR company..its a big company here..
i didnt register the phone as a blackberry because the internet service here is alittle expensive so ive decided to wait..
the phone was working fine the first 2 weeks..then one day i get the msg "invalid sim card" ive took out the sim right away cleaned it properly put it back and it worked for antoher 5 mins..then same problem..
ive figured that if i turn off the mobile network and turn it on again it doesnt change anything, but if im taking off the battery or just turning the phone off and back on it will work for few mins and same problem will appear again..
ive tried to put the same simcard in diffrent(non blackberry phones) and it works fine...even took my sister simcard(a 6 years old simcard) and same problem after about a week of using it..
il mention again first week or two it was working just fine..

the phone didnt fall or get hit..its in perfect shape..

ive even tried to put a diffrent simcard(from israel) and it works great, even with the blackberry network, ive left it for a few days to see wat happand and it was working fine..its just super expensive to use it here...

anything i can do?
please help :(

You carrier should replace the sim card without any problems. I had some issues with my first 9700 and ATT swapped the sim to ensure that wasn't causing the problem. I'd call them and see.

ive tried to do that but it worked fine again for a week or so and it hapaand again..