sharkie,
you can check hardware (bts boards, bsc boards, abis link)
check board congestion
then perform Air or A bis interface trace in order to understand where is the actual problem. If it happens during the SDCCH phase, then it might happen during authentication, ciphering or call setup, or location update, etc. In one word, there might be a problem during the exchange of info between MS and MSC.