Upgrading vB4 thread links to vB5 format

[Raakin]

How do we convert the vB4 links to vB5 format? Is it possible to somehow do it automatically? Or do we have to manually edit hundreds of thousands posts and correct the links inside them?

[Zachery]

The old links will automatically redirect to the new ones.

[Raakin]

But they are not redirecting in our forum. We were using vBSEO earlier, so maybe that is the reason.
Our earlier thread links were in this format: forumname.com/sub-section-name/1234-thread-title.html

And now the new format is: forumname.com/forum/category-name/section-name/sub-section-name/5678-thread-title

I have also noticed that the thread id numbers have changed. If I simply change the old link to /forum/category/section-name/1234, it goes to a different thread and not the same one as it was linked earlier.