We show that real implementations of the pseudonym changing mechanism do not achieve the intended privacy goals and that it is possible to exploit the TMSI reallocation procedure to track mobile telephony users. We propose countermeasures to tackle the exposed vulnerabilities and formally prove a sufficient condition to provide unlinkability.