The pseudoness of pseudorandom number generators

The standard reference is Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Anyone with serious interest in this topic should read Knuth's extensive exposition here. In addition to theoretical discussion, he presents tests including frequency, serial, gap, poker, coupon collector's, permutation, run, maximum-of-t, collision, birthday spacings, and serial correlation.

Marsaglia's DIEHARD suite of statistical test includes birthday spacings, overlapping permutations, ranks of 31x31 and 32x32 matrices, ranks of 6x8 matrices, monkey tests on 20-bit Words,monkey tests OPSO, OQSO, DNA, count the 1's in a stream of bytes, count the 1's in specific bytes, parking lot, minimum distance, random spheres, squeeze, overlapping sums, runs, and craps.

The NIST Statistical Test Suite includes frequency, block frequency, cumulative sums, runs, long runs,Marsaglia's rank, spectral (based on the Discrete Fourier Transform), nonoverlapping template matchings, overlapping template matchings, Maurer's universal statistical, approximate entropy (based on the work of Pincus, Singer and Kalman), random excursions (due to Baron and Rukhin), Lempel-Ziv complexity, linear complexity, and serial.

As for tests that fail, as Knuth mentions when discussing a typical generator in section 3.6 p. 188 "Caution: The numbers generated by ran_array fail the birthday spacings test of Section 3.3.2J, and they have other deficiencies that sometimes show up in high-resolution simulations (see exercises 3.3.2-31 and 3.3.2-35)".

Searches for Marsaglia (George), works by him or about his PRNG tests, would uncover a lot of information. e.g.,

http://en.wikipedia.org/wiki/Diehard_tests

was found by looking for "marsaglia test".