Exchange 5.5 Service will no longer start

For some unkown reason our Exchange 5.5 services will no longer start. I was able to get the System Attendant and the Directory started but everytime i attempt to start the other 3 i recieve these errors:

Microsoft Exchange Information Store:

Could not start the Microsoft Exchange Information Store service on \\server.
Error 2186: The service is not responding to the control function.

Under Eventviewer:

MSExchangeIS - General - 1121
Error 0xfb5 connecting to the Microsoft Exchange Server Directory Service.

MSExchangeIS - General - 5000
Unable to initialize the Microsoft Exchange Information Store service. Error 0xfb5.

Microsoft Exchange Internet Mail Service:

Could not start the Microsoft Exchange Internet Mail Service on \\server.
Error 1068: The dependency service or group failed to start

Under Eventviewer:

MSExchangeSA - Monitoring - 1005
Unexpected error <<0xc0040000 - The Microsoft Exchange Server computer is not available. Either there are network problems or the Microsoft Exchange Server computer is down for maintenance. Microsoft Exchange Server Information Store ID no: 8004011d-0526-00000000>> occurred.

Microsoft Message Transfer Agent:

Could not start the Microsoft Exchange Message Transfer Agent service on \\server.
Error 2140: An internal Windows NT error occurred

Under Eventviewer:

MSExchangeMTA - Resource - 9406      
A fatal directory error occurred. Change to the maximum logging level for more details. [MTA MAIN BASE 1 15] (16)                       

I've gone through and run a consistancy check on the Information store and am getting them as consistant. I can't figure out where the problem started or how to fix it. Let me know if there is anymore information needed.

System:
Dell PowerEdge 2650
Windows NT 4.0 SP6a
Exchange 5.5 SP4

Full backup of all exchsrvr locations completed.