How important is this to him and how much patience does he have? These two questions have a direct correlation to how much will it cost.
If there is no relationship, that is there are no segments of any length in common, then there is most probably no relationship between these two cousins. Technically, in this case you still don't know if there is a problem with her tree or his, but we could probably rely on hers being valid.
If there is some relationship, then you can say that he shares at least one common ancestor. Technically it could be either the 2nd great-grandfather or the 2nd great-grandmother, but it could also be both.
If money were no object, I would have him test at all 3 major autosomal services, and get a yDNA and mtDNA test(for his mother's side) first. I would test her on one of these sites.
Otherwise, I would test at AncestryDNA and have his tree online. He would look to see if any of his matches trees will help him. I would then transfer the Raw Data to FTDNA.
I do think he will find his answer if his female cousin also tests, preferably using the same service.
I would also test his Y-STR at FTDNA, at any level. He can always upgrade later.