We recently ran into an issue where we were receiving the error while trying to install update rollup 16 on a CRM 4.0 server:
Action Microsoft.Crm.Setup.Common.UpdateAction failed. The INSERT statement conflicted with the FORGEIN KEY constraint “lk_timezonerule_timezonedefinitionid”.
Missing Time Zones in the db,
1. Backup all of the CRM databases.
2. Uninstall all Rollups from the CRM Server.
3. Run the following SQL statement against all the _MSCRM databases (they are all currently Revision 2138 as you had verified)
Set Revision = ‘3’
4. Install UR1
5. Install UR9
6. Install UR16
Happy CRM’ing from the CRM Experts at PowerObjects