I've actually never read NKS but I did read this review of it which has some criticism - http://bactra.org/reviews/wolfram/

> "As the saying goes, there is much here that is new and true, but what is true is not new, and what is new is not true; and some of it is even old and false, or at least utterly unsupported."

The author seems fairly knowledgeable on the subject of cellular automata.

EDIT: I see this has been posted elsewhere in the comments