El programa es Subtitle Workshop (gratuito) y lo pillas aquí:
http://urusoft.cjb.net
Ahora no estoy en casa pa decirte cómo va, pero mira que es muy fácil de usar. Tienes que marcar el tiempo (o frame) donde empieza un subtítulo, el tiempo (o frame) en que se oculta y luego poner el texto que debe salir.
Te recomiendo que lo hagas en formato MicroDVD, ahí debes indicar los dos frames y el texto, más que nada pq otros formatos piden que metas el tiempo, y hay que teclear más que si metes el frame.
Ah, no te olvides de marcar los fps a que van a estar. Si la peli es de 25fps pues eso...
Por cierto, ¿te funcionaron los codec?
Saludos