Ah, the classic "we used a different method and got a different result" conundrum...
Which limit has been exceed?
If your specification (and indeed the associated regulatory standard, since you've made reference to one) sets a limit defined against a specific method, and the results of tests using that method are within specification, then the product would appear to be within specification, at least at face value.
Of course this does assume either a homogeneous distribution of organisms within the batch, and/or a suitable statistical sampling plan to ensure that the results are genuinely representative.
The notion that both methods give similar results is perhaps questionable here given that one is showing product in spec, and one is showing it out of spec (possibly), but this could equally be reflective of variation throughout a batch - if the methods genuinely give comparable results, and have both been followed correctly, then a logically probable conclusion is that both sets of results are correct for the particular samples of material analysed and thus the material potentially is out of spec.
Do you have retained product samples, and if so, have you had these analysed using both methods, ideally by an accredited external lab?
Have you reviewed hygiene/process records for the batch in question?
Some more detailed information about the levels and methods might be useful for further comment from forum members, but in terms of the initial response to the customer I'd simply be saying "we are investigating this and will respond with further details in due course" (and confirming whether their results are internal or from an external accredited lab) whilst you press on with arranging analysis of retained samples, review the production process for the batch etc.