In the book by Chuang and Nielsen they prove that controlled U operations can be made out of CNOTs and single qubit gates. But then they go on to prove that they are universal by showing that every n by n matrix can be decomposed into two level matrices and then to CNOTs and single qubit gates. But if so, then why can't we prove this way that controlled U can be too, decomposed to them. Since a controlled U is after all an n by n matrix. Why is there a separate proof for them?
Constructing controlled-U out of single qubit rotations and cNOT is part of the proof of universality of single qubit rotations and cNOT.
The bit of Nielsen & Chuang that you're referring to decomposes an arbitrary unitary in terms of gates such as controlled-controlled-....-controlled-U. See, for example, Fig 4.16 (P. 193 of 2002 printing). But that gate is built out of controlled-U. See, for example, Fig. 4.10 (P. 184). (although Exercise 4.28 gives you a different construction without work qubits). So, you need to construction of controlled-U for the whole thing to work.