Is it a red flag for a PhD program if their graduating students cannot find postdoc?

I'd recommend trying to gather some objective data on outcomes. For example, in the mathematics genealogy project you can search by "name of school" and "year of degree" to find a list of people who graduated in 2014 or 2015. It's not guaranteed to be complete, and it sometimes mixes together people who were in different departments at the same university, but it's usually pretty good (and sometimes easier than finding this information on math department websites).

Then you can start googling people, with "math" appended if necessary, to see what you can find. If you can't find any indication that someone is working in academia, then they probably aren't. If they are, then you can gauge how pleased you would be with such a job.

This should give more reliable data than self-reported difficulty of finding postdocs, because it avoid filtering through the departmental culture. Some cohorts of grad students are optimistic and enthusiastic, while others are more apprehensive, and it's not clear to me that this correlates particularly well with actual success on the job market.

It's also worth keeping in mind that the relevant issue is job opportunities, not actual outcomes. If one person complains about the difficulty of finding a job and another doesn't, you can't conclude anything without knowing where they were applying. (Sometimes students at more prestigious universities apply mainly to fancier postdocs, because they wouldn't be happy with less prestigious jobs.) Unfortunately, this is more difficult to gather objective data on, but I think it's a second-order effect.

This sounds like pretty thin evidence on which to base an important life decision. You don't think the graduate students at the second institution might have been a little selective in their memory? They aren't exactly unbiased observers. Let's just recap:

1. you're considering a general impression, not based on data (and thus, easily biased)
2. of presumably a few graduate students out of many in the program
3. about a 2 or 3 year period (so even for a pretty large school, maybe 50 graduates, and at many schools more like 20)
4. about a wildly variable phenomenon (since the strength of graduating classes, the number of jobs available in different fields, which advisors students worked with can all vary wildly from year to year).

Of course, all the data you have about graduate programs is low quality (since you don't know how it will apply to you, and sample sizes are so small), but if we reason Bayesian-ly, that means we shouldn't be eager to discard our priors over one data point. If the other things you know point you to first school, I don't think this is a good reason to change your mind.