Harmy said:

Use Subtitle Workshop - if it's the same cut but different speed, you can set the time of first and last subtitle and then it moves all the other subs accordingly.

Sounds wonderful! I never did get this function to work properly when I used SubtitleCreator, will have to try that program. The problem with my file though is that I took the subs from the 2004 DVD and just inserted the "new" lines in the correct order, and deleted the lines in that cut. So it's not a matter of PAL vs NTSC, just a subtitle project in its infancy.