[Kelly Rinne] "or that I am using the wrong settings?"
Not so much the wrong settings, but maybe not the best process. I would use Windows Media File Editor (a small app that comes with Windows Media Encoder 9) to create 2 files, a small one for overlaying your title and a longer 3 hour 38 minute one. This is done without recomprssion.
Use Premiere to overlay a title on the short file and export this with the same settings as the source.
Then use a video joiner like Movie Joiner (rejump.com) to join the 2 sections together without recompression.
http://www.video2stream.com
