The Trojan asteroids of Jupiter and Neptune are likely to have been captured from original heliocentric orbits in the dynamically excited (hot) population of the Kuiper belt. However, it has long been known that the optical color distributions of the Jovian Trojans and the hot population are not alike. This difference has been reconciled with the capture hypothesis by assuming that the Trojans were resurfaced (for example, by sublimation of near-surface volatiles) upon inward migration from the Kuiper belt (where blackbody temperatures are $sim$40 K) to Jupiters orbit ($sim$125 K). Here, we examine the optical color distribution of the textit{Neptunian} Trojans using a combination of new optical photometry and published data. We find a color distribution that is statistically indistinguishable from that of the Jovian Trojans but unlike any sub-population in the Kuiper belt. This result is puzzling, because the Neptunian Trojans are very cold (blackbody temperature $sim$50 K) and a thermal process acting to modify the surface colors at Neptunes distance would also affect the Kuiper belt objects beyond, where the temperatures are nearly identical. The distinctive color distributions of the Jovian and Neptunian Trojans thus present us with a conundrum: they are very similar to each other, suggesting either capture from a common source or surface modification by a common process. However, the color distributions differ from any plausible common source population, and there is no known modifying process that could operate equally at both Jupiter and Neptune.