This really looks like a combination of SIM+TSIM+phone+network. Probrably quite complicated one and without having this SIM+problematic phone and using some analyzer we cannot do much.
I had the same exact problem with a SIM visually the same as the n3 shown here. After swapping it to a newer type of 3g sim card (visually the same as the one that AT&T had) I still had the proble ...