Is "A New Kind of Science" a new kind of science?

I think the answer to this question is, unfortunately, a little difficult. As many will point out, Wolfram is beyond egotistical and that fact definitely colors the reception of the book. There is a long list of (mostly negative) reviews here. The negativity reaches its apex in the review by Cosma Shalizi. There are some positive reviews as well, though, such as the one by Rudy Rucker.

So, what is NKS? Most correctly, I would say that it is a broad and semi-popular account of Wolfram's work in cellular automata. For those in the field, it clearly builds on the work of others. There are references to this fact in the text but it could certainly be made more explicit. To more clearly see Wolfram's own contributions, you might examine his earlier collection of papers Cellular Automata and Complexity. Rucker lists several of these in his review as well. An honest assessment of his earlier contributions reveal that he is certainly an important researcher in the field and most researchers would be happy to have his body of work. Given the clear antecedents, however, I think that "New Kind of Science" is a definite overstatement. He is in no danger of winning an Abel or Nobel prize.

So, the truth of NKS is certainly somewhere in the huge gulf between a revolutionary (well) new kind of science and (as Shalizi puts it) "utter bat shit insanity".

After reading the reviews that were linked in the comments [1] and @Mark's helpful answer[2][3], I came to a a few conclusions, that answer my questions.

First, let's get something out of the way. Stephen Wolfram is definitely a polariser of opinion. Plus his way of presenting himself and his work are not in the canons of the scientific literature and that is bound to make people upset. Plus, the habit of not mentioning other people's contributions and the legal actions make it more so. But the question is not about Wolfram, the question is about the book and the ideas.

Novel Ideas

It seems to me that the most novel aspect of NKS is the proposed "paradigm shift". Namely, that to proceed in Mathematics and Physics we should abandon constructing more complicated and sophisticated theories. Instead, we should focus our attention to simple programs, such as the Cellular Automata (CA), and instead of trying to prove properties of these, we can learn about them by looking at outputs of simulations.

The validity of this paradigm remains to be proven because, according to the 3 reviews I have read, no real predictions have been made.

Another novel part of the book seems to be the "Principle of Computational Equivalence". It basically means according to [1] that there are two classes of computations: the simple/easily predictable ones, and all the "computationally irreducible", equivalent to each other. This implies that all CA complex enough, or rather, complex looking enough, are Turing equivalent. This principle, apart from not being well defined in the book, also seems to be false, according to the reviewers.

Work has already been done

Turns out a lot of work had been done on CA at the time of publishing. This has been done with the "Old Kind of Science", i.e. with proofs and all. In particular Conway's work on the Game of Life, and the fact of it being Turing equivalent. NKS does contain a lot of info and discussion about 2D CA and other programs, with links to the real world. Some of this is original, some is not.

Then there is the work of mathematicians in complexity theory that can be said to touch the same concepts as NKS.

In the end, NKS does appear to be a repackaging of ideas, in order to call to a new paradigm of doing science. If this will work, remains to be proven.

Sources

[1] A very useful, balanced and justified review. Recommended. http://www.ams.org/notices/200302/fea-gray.pdf

[2] Negative review. The arguments about the content are convincing. http://bactra.org/reviews/wolfram/

[3] Positive review. Not as balanced in my opinion. I was not convinced by it. http://sjsu.rudyrucker.com/~rudy.rucker/wolfram_review_AMM_11_2003.pdf

The problem is that asking if something is novel in science is actually very tricky because almost every scientific idea is based on previous work. Therefore, I don't think it is very valuable to question whether something is novel or not because it most certainly is not. However, you can ask if a particular work offers something interesting or particularly noteworthy. I will enumerate a few prominent ideas explained in NKS, including previous work (which is more or less what you asked):

1. A proposed method to analyse complex systems is to explore the computational universe to see what simple programs are able to do and document their behavior using experimental or analytic methods. Previous work: Edward Fredkin and Konrad Zuse proposed the idea that the universe might be a cellular automaton. In 1997, Schmidhuber described a Turing machine capable of computing all possible histories for the universe based on physical laws.

2. Principle of computational irreducibility. Systems that display complex behavior can not be reduced and we need to run the experiment to see the outcome.

3. Principle of computational equivalence. Most sufficiently complex systems are computationally equivalent.

4. Turing completeness of Rule 110. Wolfram conjectured this in 1985. Matthew Cook (who worked as a research assistant to Wolfram) published a proof in 2000 and a legal battle ensued due to a violation of an NDA. Previous work: Conway's Game of Life, Von Neumann's idea of self-replicating machines.

5. Conjecture that the 2-state 3-symbol Turing machine is universal. Alex Smith proved this conjecture in 2007.

There are other interesting ideas but most of them are extremely speculative and unlikely to be confirmed or falsified by evidence any time soon.