it sounds like it's been encoded as part of the video, so the only way to remove it is to physically erase it from the video using a filter, this will never give a perfect result, but it can be done.
Here's a tutorial showing how to remove text elements with the free programs VirtualDubMod ( download:
here) and MSU Subtitle Remover (download link is on the tutorial page):
http://www.compression.ru/video/subt.../index_en.html
This works by attempting to re-create what was underneath the titles, might be a bit blurry though.
You could of course just cover them in Prmeiere Pro by perhaps duplicating the video clip, placing the copy on the layer above the original then cropping it and moving it so the text is covered by another similar region of the same frame, then feather the edges.
Someone else might have a better suggestion though...