R help - Feb 2007 - interacting factors in lmer [was: error using user-defined link function]

For what it's worth, I've been getting the exact same error message  
as in the previous thread (see http://tolstoy.newcastle.edu.au/R/e2/ 
help/07/02/10269.html etc.):

Error in if (any(sd < 0)) return("'sd' slot has negative
entries") :
	missing value where TRUE/FALSE needed

as well as NaN's all through the model, by using lmer on a formula  
that includes a term of the type (A | B) where A and B are factors  
that aren't robustly crossed, i.e. there are some empty cells in there.

I've been wondering in general about the relative merits and  
appropriateness of the following types of formula:

1) Y ~ A + B + A:B
2) Y ~ (1 | A) + (1 | B) + (1 | A:B)
3) Y ~ A + (A | B)
4) Y ~ (1 | A) + (A | B)

Type 1 is for fixed effects with interactions.

Type 2, logically, should be for random effects with interactions  
(except are random effects supposed to be independent, by some  
assumption of the model?)

Type 3 should be for a fixed effect interacting with a random effect.  
However, this is where I get the error message above, often,  
sometimes after 15 minutes of computer calculation...

Type 4, I'm thinking, is a variant of 2, but maybe it isn't  
legitimate since in (A | B) A is deemed to be a fixed effect?

I know type 1 is normally used and it even has a shorthand, A*B.
But when one or both effects is random, what is the best way to model  
interactions in an lmer formula?

And what is the best way to look for interactions between random  
factors when crossing them results in unavoidable empty cells?

Thanks,
Daniel