New Horizons 2 was actually included in the tentative budget for the New Horizons missions. In 2004 the United States Senate Appropriations Committee provided additional funding for New Horizons 2, a new Kuiper Belt mission. As early as 2004 there was a conference on how to make the most use of NH2's Uranus flyby.
Candidate targets included 1999 TC36, a system that, like Pluto–Charon, contains multiple bodies. The mission plan for 1999 TC36 also included flybys of Jupiter and Uranus, and perhaps four KBOs. There was a lot of flexibility: even without a gravity assist any KBO within 50 AU and a 20-year flight time was possible. A flyby of Neptune's Triton was also considered, with 66652 Borasisi as a potential follow on.