We present the discovery of a long-term stable L5 (trailing) Neptune Trojan in data acquired to search for candidate Trans-Neptunian objects for the New Horizons spacecraft to fly by during an extended post-Pluto mission. This Neptune Trojan, 2011 HM102, has the highest inclination (29.4 degrees) of any known member of this population. It is intrinsically brighter than any single L5 Jupiter Trojan at H~8.18. We have determined its gri colors (a first for any L5 Neptune Trojan), which we find to be similar to the moderately red colors of the L4 Neptune Trojans, suggesting similar surface properties for members of both Trojan clouds. We also present colors derived from archival data for two L4 Neptune Trojans (2006 RJ103 and 2007 VL305), better refining the overall color distribution of the population. In this document we describe the discovery circumstances, our physical characterization of 2011 HM102, and this object's implications for the Neptune Trojan population overall. Finally, we discuss the prospects for detecting 2011 HM102 from the New Horizons spacecraft during their close approach in mid- to late-2013.