Kolmogorov complexity is not the right criterion for statistical randomness tests, since any pseudorandom sequence has low Kolmogorov complexity. What you really want in a random number generator is for the sequence to be computationally pseudorandom; that is, without knowledge of the seed, no polynomial-time test can distinguish the sequence from a truly random sequence.
In fact, there are a number of random number generators which are believed to be computationally pseudorandom. Nobody uses these, however, partly because they are computationally too expensive, and partly because of inertia and partly because the existing pseudorandom generators we have (which pass Marsaglia's test) are good enough most of the time. For both of the two most common methods of pseudorandom number generation, however, I've run into cases where they've produced the wrong answer. See this stack overflow discussion.