The directory service has exhausted the pool of relative identifiers

New RIDs appear not to be being generated.

This suggests either the RID service is broken, or the RID master role is not correctly asigned to this server, regardless of what your checks indicate.

I'd suggest running 'netdom query fsmo' to double check the RID master role holder

Are there any errors in the event logs for services failing to start?

It's definitely telling you that it can't access the RID Master as xenny has said. DCDiag will run a set of tests that will give you a better idea of what is going on:

dcdiag /v /test:ridmanager

This will give you output similar to the following if things are OK:

Starting test: RidManager
* Available RID Pool for the Domain is 8604 to 1073741823
* mydc1.mydomain.com is the RID Master
* DsBind with RID Master was successful
* rIDAllocationPool is 7604 to 8103
* rIDPreviousAllocationPool is 7604 to 8103
* rIDNextRID: 7768
......................... MYDC1 passed test RidManager