Connection between NAND gates and Turing completeness
There is indeed little connection. For a thorough understanding, let me explain the connection between programs and circuits.

A program (or algorithm, or machine) is a mechanism for computing a function. For definiteness, let us assume that the input is a binary string $x$, and the output is a Boolean output $b$. The size of the input is potentially unbounded. One example is a program that determines whether the input is the binary encoding of a prime number.

A (Boolean) circuit is a collection of instructions for computing some finite function. We can picture the circuit as an electrical circuit, or think of it as a sequence of instructions (this view is called confusingly a straight-line program). Concretely, we can assume that the input is a binary string $x$ of length $n$, and the output is Boolean. One example is a circuit that determines whether the input encodes a prime number (just as before, only now the input has to be of length $n$).

We can convert a program $P$ into a circuit $P_n$ that simulates $P$ on inputs of length $n$. The corresponding sequence of circuits $P_0,P_1,P_2,\ldots$ is not arbitrary – they can all be constructed by a program that given $n$ outputs $P_n$. We call such a sequence of circuits a uniform circuit (confusingly, we often think of the sequence as a "single" circuit $P_n$ for an indefinite $n$).

Not every sequence of circuits is uniform. Indeed, a sequence of circuits can compute every function from strings to Boolean, computable or uncomputable! Nevertheless, in complexity theory we are interested in such non-uniform models in which the circuits are restricted. For example, the question P=NP states that NP-complete problems cannot be solved by polynomial time algorithms. This implies that NP-complete problems cannot be solved by polynomial size uniform circuits. It is moreover conjectured that NP-complete problems cannot be solved by polynomial size circuits without the requirement of uniformity.

Turing-complete computation models are models which realize all computable functions (and no more). In contrast, complete systems of gates (such as AND,OR,NOT or NAND) allow computing arbitrary finite functions using circuits made of these gates. Such complete systems can compute completely arbitrary functions using (unrestricted) sequences of circuits.