Just to give some additional information here...
I won't go too deep in it, but because of the way AD works, with USN's, the behavior of starting in Safe Mode is expected. In fact, this is the safest. Because if you would bring a DC back online that comes from an older timestamp, bad things could happen to your AD environment. That's why the people at MSFT have built this in. So following above mentioned KB is the way to go. The good thing is that you will be able to select whether you are going to do an authoritative restore or non-authoritative restore. (the KB gives you the non-authoritative...) so in case you need to "go back" with your domain to the previous situation (or you need to recover one specific object because you are not using the recycle bin
) you can do that also.