Oooch… that’s bad ! Not normal, for sure.
You’re having a configuration issue somewhere. I don’t think the BSS can be causing the trouble here (maybe it does ? you have to check if anything is related to IMSI / TMSI in the BSC or in the BTS).
So probably it’s a problem in MSC/VLR.
If you want to investigate : perform a drive test, do a call setup, and see if you can detect a failure during the SDCCH phase.
Or, better, do a trace on the A-interface. Check the Authentication / Ciphering / TMSI Reallocation procedures on this trace. You can check that for many mobiles, that’s why it is certainly better than a drivetest, that shows result for only one mobile station.