In the current model of early Solar System evolution, the stable members of the Jovian and Neptunian Trojan populations were captured into resonance from the leftover reservoir of planetesimals during the outward migration of the giant planets. As a result, both Jovian and Neptunian Trojans share a common origin with the primordial disk population, whose other surviving members constitute today's trans-Neptunian object (TNO) populations. The cold classical TNOs are ultra-red, while the dynamically excited "hot" population of TNOs contains a mixture of ultra-red and blue objects. In contrast, Jovian and Neptunian Trojans are observed to be blue. While the absence of ultra-red Jovian Trojans can be readily explained by the sublimation of volatile material from their surfaces due to the high flux of solar radiation at 5AU, the lack of ultra-red Neptunian Trojans presents both a puzzle and a challenge to formation models. In this work we report the discovery by the Dark Energy Survey (DES) of two new dynamically stable L4 Neptunian Trojans,2013 VX30 and 2014 UU240, both with inclinations i >30 degrees, making them the highest-inclination known stable Neptunian Trojans. We have measured the colors of these and three other dynamically stable Neptunian Trojans previously observed by DES, and find that 2013 VX30 is ultra-red, the first such Neptunian Trojan in its class. As such, 2013 VX30 may be a "missing link" between the Trojan and TNO populations. Using a simulation of the DES TNO detection efficiency, we find that there are 162 +/- 73 Trojans with Hr < 10 at the L4 Lagrange point of Neptune. Moreover, the blue-to-red Neptunian Trojan population ratio should be higher than 17:1. Based on this result, we discuss the possible origin of the ultra-red Neptunian Trojan population and its implications for the formation history of Neptunian Trojans.