Jonah,
If I recall correctly, the help outlines a couple of different methods related to using your own templates. One is via publishing an Export Web Map gp print task. The other is discussed under the umbrella of "advanced printing". Are you talking about the Export Web Map gp task when you say "...published...a geoprocessing service"? If so, you either save your mxd templates in a folder or let ArcGIS Server copy them onto the server (recommend the former) per the instructions in help. The config file entries for the Flex viewer are really minimal, regardless if you use the Application Builder or the source code.
I suspect you were following the help related to the "advanced printing", as the result is something that you then need to program your own front end to use effectively. Just my opinion.
I effectively serve up letter-sized to E-sized templates to my users with the Export Web Map print task, with excellent results just by following the instructions in help carefully.
