I understand this is an older post but I was struggling with this same issue over the past couple days and have found a solution I thought I would share.
The trick is in understanding how the CQWP actually builds the XML structure. You can see this by editing the ContentQueryMain.xsl (found at /Style Library/XSL Style Sheets) by adding a new template that overrides all the others to view the raw XML data.
NOTE: As always, the best practice is to make a copy of the file and call that with your custom web part. Also, remember to change this back when done otherwise all your CQWP on the site will just show the XML rather than the formatted view!
<xsl:template match="/">
<xmp><xsl:copy-of select="*"/></xmp>
</xsl:template>
Also you can enable automatic indenting on the template by finding the changing the line
<xsl:output method="xml" indent="no" />
to
<xsl:output method="xml" indent="yes" />
Save and check-in the file and then re-load the page with your CQWP. You should see a well formatted plain text outline of the data being queried
<dsQueryResponse>
<Rows>
<Row ListId="LIST_GUID_1" WebId="GUID" ID="1" parameter1="value1" parameter2="value1" Style="MyStyle" GroupStyle="MyGroup" _begincolum="True" _begingroup="True" />
<Row ListId="LIST_GUID_1" WebId="GUID" ID="2" parameter1="value1" parameter2="value2" Style="MyStyle" GroupStyle="MyGroup" _begincolum="False" _begingroup="False" />
<Row ListId="LIST_GUID_2" WebId="GUID" ID="3" parameter1="value2" parameter2="value3" Style="MyStyle" GroupStyle="MyGroup" _begincolum="False" _begingroup="True" />
<Row ListId="LIST_GUID_2" WebId="GUID" ID="4" parameter1="value2" parameter2="value4" Style="MyStyle" GroupStyle="MyGroup" _begincolum="False" _begingroup="False" />
</Rows>
</dsQueryResponse>
Looking at this we can see that the XML is structured without a break between items of different groups, which is why the basic count(.//Row) doesn't work. Instead what we need to do is walk back to the parent ("Rows") and get a count of "Row" that has been filtered to find only items like the one of the group we are currently counting. In this example, we are grouping by "parameter1" so we will want to get a count of items where parameter1 matches the value of parameter1 of the current item (which in the header will be the first item of a group). Here is the line of code in the Header.xml in the custom "MyStyle" template:
<xsl:value-of select="count(..//Row[@parameter1 = current()/@parameter1])"/>
And that's it! Put that where ever in your header template you want the count to appear and you should be all set!