I want to thank everyone for the help and input. You have certainly pointed me in the right direction as I have finally found a solution.
After testing a demo of every Mapping and CAD application that I could find that will handle 3D Geo data, I have finally found one that will easily interpolate elevations into my routes,
Global Mapper 12 (I'm not sure if previous versions also have this functionality!). It offers the following two options for completing elevation data while viewing the route information:
1. Evenly spread elevations between first and last elevations.
2. Interpolate elevations to replace 0 values.
Option 2 works perfectly on the data that I plan to use.
It also has a function to complete elevations from loaded DEMs, this may be useful if you are using 1/9 Arc DEMS for your terrain, but using 1/9 arc in TransDEM seems to handle this pretty well already.
The only downside to Global Mapper is the cost, at 349 US, it's a steep price for me to only gain this one function. So I may find myself being rushed to collect my route data before the Time Limited Trial expires (I don't know how long that is yet, I haven't gotten the Trial key yet!). It may be worth the cost if I can find another use for it though.
I hope this information helps someone else, as this has been a headache for me. Now I have to uninstall some 30 applications off my PC.
Again, thanks for all the help