The notion of locality that Deutsch is trying to establish is his interpretation of Einstein locality, the statement that the "actual physical state of a system" is not modified by the actions one performs on far away systems.
The way Einstein meant it, this principle is just plain false in quantum mechanics. Einstein's interpretation of "actual physical state" is called "local hidden variables" nowadays, it tells you the outcome of all measurments on the system. Local hidden variables are ruled out by Bell inequality violations.
But Deutsch takes a more liberal view of "actual physical state", identifying it with the best-possible quantum description of a system. Deutsch is saying something well known--- namely that quantum mechanics is compatible with a version of locality, namely that the best-possible quantum description of a system, ignoring other disconnected systems, doesn't change no matter what you do to the disconnected systems. The best possible quantum description of an entangled system is the reduced density matrix, and if you think of this as the "true state of the system", then this true state doesn't change in response to anything you do far away.
Deutsch makes this argument more cleanly than usual, by using a quantum computer with two disjoint collections of qubits isolated from each other. This is nice conceptually, but its really no different than the usual version, where you have two regions of space with commuting quantum field operators which correspond to measurements in the separate regions. In both cases, the operators associated to the disjoint sets commute, so that measuring one, or acting using an operator constructed from one set as a Hamiltonian, will do nothing to the density matrix of the other.
This type of locality is well known, but it is not completely obvious, because the wavefunction is a global thing--- it describes the whole system, entangling the parts. The existence of local observables guarantees that you can't use this to send signals faster than light, or do anything else nonlocal either.