For what sorts of reasons would a university deny an application to a graduate program in the U.S. after the department recommends it for admission? I'm in the process of applying to Ph.D. programs right now, and professors from two schools have let me know that I've been recommended for admission and that the graduate studies department still had to approve the recommendation. In both cases, I was assured that there was no way the approval would be denied. 

I don't have any red flags in my application, so this is a question out of pure curiosity. How often does it happen that the graduate school at large goes against the recommendation of the departmental committee, and for what sorts of reasons would this happen?
In both the private and public R1s that I've been in (in the USA), the departments run admissions. They read through the applications and then send the graduate school their ranked list of admits, a rolldown list, and the list of rejects.

However, technically the department does not admit students, the graduate school does. So the department list are only "recommendations."

I would say that 99% of the time, the graduate school acts on those recommendations. They'd be fools not to, since the disciplinary expertise is in the department.

The 1% that I've personally experienced was with a graduate student who had horrible GRE scores but other stellar qualifications. Despite our university annually sending us guidance saying that GREs are not correlated with graduate school performance, very low scores could be cause for concern in their office (likely because of national rankings, but I have no insight there).

The dean of the graduate school wrote to us about that student and held up their admission. We had to write a response as to why we felt other aspects of their application overrode their poor GRE scores, and the student was admitted. But the experience did make it clear that the graduate school does look over admits, and might step in for extreme cases -- and why we have to be careful in our communications with students that we're only recommending admission.

Another scenario that might apply is that the graduate school changes its calculation midcycle in terms  of how many slots a department might have, or how much funding is available to students (cutting, for example, some fellowship slots). I haven't heard of this happening, but I would imagine the grad school reserves the right to pull such a maneuver, especially as we are asked to submit ranked lists and so it is possible that the 13th student in a 13 member list might be sent off the island in some scenarios.