The impetus for this particular post was that it was somewhat surprising that counts were still doing full scans, even if the query conditions were on an indexed field. My expectation was that the index might have some information on how big a particular part of the index tree is (given two bounds), but it turns out that it doesn't, so you end up looking at each document and doing inspection per row. This isn't normally a problem, but the comparison is relatively slow, so the whole thing starts to drag down faster than you'd normally expect.
When the problem is hidden below several levels of library/ORM candy coating, it's not going to be immediately obvious that this is a problem, especially if the queries against that field are otherwise performant thanks to proper use of indexes. It's non-obvious, and given that someone else found it interesting enough to post here, I'm apparently not the only person in the world to ever have this problem. There are multiple open tickets in the Mongo JIRA system, as well as multiple discussions on this topic on the mailing list. This isn't me whining that 10gen won't fix my software, it's an acknowledgment of the problem and steps towards fixing it.
10gen themselves have acknowledged via the mailing lists that counts are slower than they should be, and it's on the list of things to improve. Until then, we have to make do with workarounds.