The main question is how do you map the CA to reality? You need to say how you describe an experimental situation in terms of the CA variables. If the map is such that an atom is described by a local clump of automata variables, and a far-away atom is described by another local clump of automata variables far away, it is flat out impossible to reproduce quantum mechanics, even in a crude way. This type of model is thoroughly ruled out by Bell's inequality violation.
But there is no requirement that the map between atomic observables and CA variables is local. If you imagine that the CA is on the surface of a holographic screen (as t'Hooft often liked to draw), then any one atom can be described by gross properties of essentially all the CA variables, nonlocally, while another atom far away is also described by a different property of all the CA variables together, so that they are always interacting. But it is concievable that statistically, those properties of the CA that describe each atom individually look like they obeying a wavefunction time evolution.
This type of thing is very hard to rule out, at least, I don't know how you would show that this sort of thing can't reproduce quantum mechanics to the extent that it has been measured.
This is something I wonder about off and on. Is it possible, even in principle, to find a CA with a physical number of variables, on the order of the cosmological horizon area divided by the Planck area, which reproduces the observed predictions of quantum mechanics by a horrendously nonlocal identification between the properties of objects and the CA variables?
It is certainly impossible to reproduce all of quantum mechanics with a model of this sort. Shor's algorithm for factoring 10,000 digit numbers will certainly fail, because there aren't enough bits and operations in the CA to do the factoring. But we haven't built a quantum computer of this size yet, so that this may be seen as a safe prediction of all such models--- that quantum computers will fail at a certain not-so-enormous number of qubits.
So it is impossible to reproduce full QM, but it might be possible to reproduce a cheap QM, which matches the cheap QM we have observed to date. You must remember that every time we verify the prediction of QM, we are not in a regime where it is doing an exponential computation of large size, precisely because if it were, we wouldn't be able to compute the consequences to compare with experiment in the first place.
The nonlocality can be in space and time together. For previous answers regarding related stuff, see here: Consequences of the new theorem in QM?