Another idea that might be worth trying is a subquery:

select count(*) from theTable
where column1 in
  (select column1 from theTable
   where column2 = 123)
and column2 = 124
[download]

But the other suggestion would probably scale better for bigger groups of attributes.

Update: By the way, practically everyone who answered is giving you the wrong impression about indexes. Sometimes sequential scans are faster than using indexes, for example if the attribute being tested is a match for a large percentage of the records. That's what the query optimizer is supposed to do on a query-by-query basis: decide whether to use the indexes or not, and in what sequence. In the subquery I suggested above, the optimizer might not be smart enough to do it, so you might have to create the query such that the smallest subset will be selected by the inner query.