Windows 2003 Small Business Server reports The Active Directory is rebuilding indices. Please wait…
Once complete login into server and attempting to start Active Directory Users and Computers report errors. A number of key services not starting.

To correct the issue the Active Directory database was fixed using ntdsutil as follows:

1. Booted server in Directory Service Restore Mode using F8 on boot up
2. Moved the log files from c:\windows\ntds\. (Do not move NTDS.DIT, this is the AD Database)
3. Type ntdsutil files integrity (Checks integrety of ntds.dit)
4. Type ntdsutil “sem d a” go
5. Type ntdsutil “sem d a” “go f”

Reboot server to see if issue is corrected.
If not continue

You can use Esentutl.exe to perform database recovery when the procedure described earlier in this article fails (for example, the procedure may fail when the database is inconsistent). To use Esentutl.exe to perform database recovery, follow these steps:

1. Type esentutl /r c:\windows\ntds\ntds.dit
2. Delete the database log files (.log) from the WINDOWS\Ntds folder.
3. Restart the computer.

Reference: http://support.microsoft.com/kb/816120
 
If all else fails then you must run the following command. Note that this command will delete entries in the Active Directory Database and may affect the server. In our case, it did fix the issue, but then the Symantec Backup Exec and End Point Protection services would not start. Had to reinstall the two Symantec products.

1. Run the command  esentutl /p “c:\windows\ntds\ntds.dit”
2. Restarted the server – issue is fixed

Reference: http://support.microsoft.com/kb/258062