It's really bad if forum id changed in the db.
And this can only come from the backup (either when backing it up or when importing it), unless of course, someone did all this in the acp, but I kind of doubt it.
So, there is no easy way to deal with that, as said, it can be problematic to keep this db as imported online because many other things, such as auth, later depend on forum ids.
So unless someone did the id change in acp (eg delete / re create all forums) then all other table depending on this where not updated while importing the db and are most likely messed up right now.
I think that the best thing to do would be to close the forum for some time, and create a local install of phpBB to import your backup in it to find out how badly thing where messed up.
Because for indexing, these new urls are like new pages, it's actually like if you had dropped all your forum and recreated new ones for bots. And there is no easy way to implement the redirect since you'd need to know all the old / new forum id associations.
The matter could be related to auto-increment being saved in the forum db backup, and no drop / create performed on this table. If you do not drop the forum table before you recreate it, all the data inserted later could start from the last auto-increment value, but it would as well imply that the insert do not mention any forum id, which would be the sign of a deficient backup.
Contacting your forum hosting service, the bug could come from them. How was this db backup performed ?
To help you more, I'd need to see at least the beginning of forum table dump you have, table structure and one complete insert (with a not passworded forum insert, no sensible data will be in there).
You can post PM me a zip;)