Unable to synchronize users after database restoration in NAV

Above is not correct.

You need to do the “Compare & Merge” step in-between your above mentioned steps.