I recently installed Microsoft Dynamics CRM 4.0 server on a Windows Server 2008 R2 x64 machine and it completed successfully. Referencing the Microsoft KB Article on Support for Microsoft CRM 4.0 on Windows Server 2008 helped.
However, I then encountered the following error "An entry with the same key already exists" when trying to access the CRM Client Settings >> Administration >> System Settings:
Resolution: This is a known error when installing CRM server on a Windows Server 2008 R2 (2008 is OK) and applying the latest Update Rollup solved this issue. As a good practice – apply the latest update rollup on a new CRM installation.