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.