Just to be clear: in this case I need to get all elements that have both one element of stuff that has foo set as 1 with bar set as "a" and also one element of stuff that has foo set as 2 with bar set as "b".
I hope I got it. Shouldn't that be
db.coll.find({ $and: [
{ "stuff" : { $elemMatch : { "foo" : 1, "bar" : "a" } } },
{ "stuff" : { $elemMatch : { "foo" : 2, "bar" : "b" } } } ]});
?