I don't know about combinatorics in particular, but I did get a PhD from one of Carnegie Mellon's other interdisciplinary programs (Pure and Applied Logic); I was offered the choice of whether my PhD would officially be in the program name or in "Mathematical Sciences", and was advised to choose the latter.
If you're PhD is in something other than "Mathematics" or an obvious synonym, and you want to get hired as mathematics faculty, there are two concerns that might come up:
Do you know enough math, broadly speaking, to be a good colleague (for instance, be out outside member on thesis committees, to talk to people, and so on)?
Can you teach introductory courses?
I do know of people with degrees called "Logic" where these concerns were raised about hiring them. In the cases I know, someone was around to address those concerns, but it might be a disadvantage in departments where no one in the faculty was familiar enough with the program to address them. (On the other hand, places where no one is familiar with your program aren't as likely to hire you anyway.)
With a degree in something as clearly mathematical as combinatorics, I think the first concern is unlikely to be an issue. The latter might be, especially if those programs don't necessarily include any TA-ing/teaching of intro calculus courses, but this is also a concern that can be preempted (for instance, by making sure to pursue enough teaching experience as a grad student).
