"Do you mean that when I lock the chip, I cannot read from code space?

If so, I do not believe this is true. Otherwise code would not run."

Why not? You may not be able to read from code space but that won't stop the CPU from doing code fetches. I would guess that MOVC is treated as a sequence of NOPs.

One of the lock bits prevents the use of MOVC in certain situations. I *think* the idea is to prevent a 'hacker' from attaching an external ROM containing a program which then reads out the internal code space. Presumably this would require EA to be toggled at just the right moment.

I've no idea whether this is your problem or not, it just seems a bit of a coincidence that the only problem you have seems to be with MOVC and these Atmel parts have that lock bit.