Hello,

I have a problem with Countif, and that is it seems to only work where the
criteria is 255 characters or less.

Yes, Countif and Sumif only accept 255 characters here.

[A German link: http://www.xlam.ch/xlimits/worksheetfunctions.htm]

As already suggested, you might want to use Sumproduct:
http://sulprobil.com/html/countif1.html

Regards,
Bernd