SIM compatibility problem. PL HELP

I have been using Ufone SIM in Pakistan successfully in my Nokia 6681. Now I've switched over to Telenor. After inserting Telenor SIM, i am unable to access menu on my Nokia 6681. Each time I press the menu button, "Menu" writing appears on phone and all of a sudden it gets back to original screen (with active standby icons, battery bar and signal bar). After starting Nokia 6681 in "offline" mode, I can access the menus but each time I open a folder, error is displayed "Cannot delete the folder". I tried many other Telenor SIM, each gives errors. I used another Nokia 6681, same error there. The problem is due to SIM. Can anybody help how to rectify the problem. I'll be very grateful.