Edit: Simple solution (credit goes to SaintWacko)
Concatenate the two columns:
Create a pivot table, using the concatenated column as a 'Row Label' and a 'Value'. Then make sure the 'Value' is calculating counts (should be default).
You can concatenate the two columns in column C:
In column D, you'll need a function that determines if the item is a duplicate of another item so that the value is true for only one of each item (this only works if the items are sorted by the data columns, but the macro later does that).
Then calculate the count if matched in column E:
A macro will find all combinations for you, place them on sheet 2 and copy the counts. The code below makes some assumptions, but you can probably modify it to do what you need.
Dim sheet1, sheet2 As Worksheet
Set sheet1 = Worksheets(1)
Set sheet2 = Worksheets(2)
Dim sStartColumn As String
Dim iTopRow As Long
Dim sEndColumn As String
Dim iBottomRow As Long
sStartColumn = "A"
iTopRow = 1
sEndColumn = "E"
iBottomRow = sheet1.UsedRange.Rows.Count
Dim Rng As Range
Dim sRange1 As String
sRange1 = sStartColumn & CStr(iTopRow) & ":" & sEndColumn & CStr(iBottomRow)
Set Rng = sheet1.Range(sRange1)
Rng.Sort Key1:=Range("A2"), Order1:=xlAscending, _
Key2:=Range("B2"), Order2:=xlAscending, _
Dim i, j As Integer
j = 2
For i = 2 To iBottomRow
If sheet1.Cells(i, 4) Then
sheet2.Cells(j, 1) = sheet1.Cells(i, 1)
sheet2.Cells(j, 2) = sheet1.Cells(i, 2)
sheet2.Cells(j, 3) = sheet1.Cells(i, 5)
j = j + 1
That should do it.