Agora há outra otimização além de criar um índice adequado.
db.users.ensureIndex({name:1});
db.users.find({name:"Andrei"}).count();
Se você precisar de alguns contadores, sugiro pré-calculá-los sempre que possível. Usando a operação $inc atômica e não usando
count({}) de forma alguma. Mas os caras do mongodb estão trabalhando duro no mongodb, então,
count({}) melhorias que eles estão planejando no mongodb 2.1 de acordo com o bug do jira. 
