COUNT (distinct) is actually a single reducer problem and goes through a massive reduce side sort. Therefore, even the "reduce" method becomes an expensive and all in-memory operation. So if you are operating on several TBs of data - it might take an excessively long time.
A good alternative to this would be -
SELECT count(*) from ( SELECT distinct <col_list> from table ) t1;
This query will generate two Map Reduce jobs:
1. In the first one it will be doing PARTITIONING and using all the reducers, and
2. In the next Map Reduce job it is still a one-reducer problem but it only does COUNT( not count distinct ) so pretty light weight operation ( with map side aggregation ). Hence this finishes really fast.