Counting Combinations in Excel

Dear LazyWeb, I have a spreadsheet laid out as follows:
1 User First Second
2 turing red up
3 hopper blue down
4 zuse red up
5 knuth blue up
I'd like to generate another table counting choice pairs:
100 101 102
X red blue
Y up 2 1
Z down 0 1
There are going to be about eight values for 'First', and about a dozen for 'Second', so I don't mind typing in the row/column headers for the second table. What I want is something like a double-barrelled COUNTIF(), but there doesn't appear to be one. I've tried constructing an extra column joining the two choice values:
1 User First Second _joined_
2 turing red up red:up
3 hopper blue down blue:down
4 zuse red up red:up
5 knuth blue up blue:up
and then doing COUNTIF(D2:D5,=CONCATENATE(something,':',something)). However, I can't put a CONCATENATE or any other function call in the second half of a COUNTIF (though you can compare to a cell value using something like ">="&A5, and yes, the quotes are supposed to be where they are). I also can't figure out what the something's should be to look up the two items to concatenate. So, how should I do this? And please don't say "use a relational database" --- I've got some constraints here.