This is happening to so many people that Microsoft has updated KB940157 and posted on the MU blog:
Note To install Windows Search 4.0 successfully on a computer that is running Windows XP or Windows Server 2003, Terminal Services must be running on the computer. Also, Terminal Services must be running for Windows Search 4.0 to function correctly. By default, Terminal Services is configured to start automatically. However, it may have been disabled manually or by third-party software. If Terminal Services is disabled, the installation of Windows Search 4.0 will fail with error code 643.