Why was it removed? Does it no longer provide sufficient testing of a PRNG or was it simply superseded by better tests?
According to the paper On Lempel-Ziv Complexity of Sequences by Doganaksoy and Gologlu,
A test based on Lempel-Ziv complexity was used in the NIST test suite, to test the randomness of sequences. However the test had some weaknesses. First of all, the test could only be applied to data of a specified length: $10^6$ bits. Moreover, the test used empirical data generated by SHA-1 (under randomness assumptions) for estimating the expected value of Lempel-Ziv complexity of sequences of length $10^6$ bits. Apparently, the data generated by SHA-1 led to not-so-good an estimate, hence, for instance, first $10^6$ bits of the binary expansion of $e$ failed the randomness test. Using asymptotic formulae for an estimate will not work either, since the sequences, as we will see in the forthcoming sections, are distributed tightly around the mean. Recently, apparently because of the spelt out reasons, Lempel-Ziv test had been excluded from the NIST test suite.
The Crypt-XS package, part of the NIST suite, includes the simply named sequence complexity test, which is based on Lempel-Ziv compression.