I am guessing VxWorks but I haven't found any sources to validate
Close, but no cigar. If New Horizons flight software was built by Jet Propulsion Laboratory (JPL), then I guess Wind River's VxWorks RTOS would have been their first choice (it's also a popular choice for hardware on Mars - Pathfinder, Sojourner, Phoenix lander, Spirit, Opportunity, Curiosity,... all use it). But New Horizons flight software was built by Johns Hopkins University's Applied Physics Laboratory (APL) and they decided to build it atop Nucleus RTOS by Mentor Graphics.
Refer to Linux and the Spacecraft Flight Software Environment, E. Birrane et al., JHU/APL (PDF) for more info. Mind that despite document's title, neither VxWorks nor Nucleus are Linuxes. I selected this document to link to as it's a good source of background information on both Nucleus and VxWorks, both commercial RTOS'es used on spacecraft, but it discusses possible evolutionary path of flight software and Linux' role in it (there are real-time Linux microkernels available, such as RTLinux), thus the title.
An overview (but oddly no mention of OS) is also available in Spacecraft Systems and Components page over at New Horizons at APL.