No data for 1 interaction combination: problem in R not in Genstat

I've found that when I do a linear mixed model either with lme or lmer 
with interactions amongst some fixed effects that if there are any 
interaction levels unoccupied with data that the model fails.
"Error in MEEM(object, conLin, control$niterEM) :
   Singularity in backsolve at level 0, block 1" for lme and

"Error in mer_finalize(ans) : Downdated X'X is not positive definite, 
6." in lmer.

Strangely in Genstat the model does produce output.
My solutions will be either to use Genstat or to create a single new 
factor variable which has the levels of the interaction that *are* 
represented in the interaction.

I haven't found anything about this when searching. I guess that this 
may be deliberate (e.g. Genstat uses a fudge considered inappropriate) 
but please could anybody advise me?
I can provide a simple fictitious example that I invented in which the 
interaction would be of interest but can't be modelled. (I haven't 
posted it here because I'm unsure about the etiquette of posting large 
e-mails containing data onto the discussion list).

Dr Roger Humphry, Applied Statistician,
Epidemiology Research Unit, SAC, Inverness
01463 246059