Is there a possibility that the document page setup has color as the default? For example, they are using a process black (CMYK) to print their Black pages. If so the process black will count as a full color page. I ran into this with a MAC installation.