When a database sync is performed, an alias regeneration process is initiated on the receiving server. If the aliases are not regenerating, an update may fix your issue.
The below issues are documented for 9.1SP2 and previous versions in the version 9 branch. To address these, upgrade to 9.1SP2 if necessary and apply the latest cumulative site update for 9.1SP2.
Update 5 (November 13, 2015)
23306 - Auto Aliases were not created on production after syncing from authoring using a bidirectional sync profile. A 'SQL Exception' error may have occurred on the destination server when the aliases were recreated.
Update 11 (December 30, 2015)
23547 - When adding a folder association mapping to the CMS for a taxonomy that has auto aliasing enabled, auto aliases are not generated.
If you are still getting 404 errors with auto aliases it is recommended to wait for some time after a sync completes as auto aliasing may still be regenerating.