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