enterprise geodatabase - ArcGIS Server Error: "Feature service requires a registered database"

I'm attempting to publish a feature service to ArcGIS server. I'm running SQL Server Express and ArcSDE. When I try to publish the service I get the error "00090: Feature service requires a registered database".

When I validate the database registration it appears to succeed, but I still can't publish the service. The features I am publishing are located inside of the geodatabase that I am registering. This geodatabase is located on the same server that ArcGIS Server resides, but I am attempting to publish from another machine. Am I missing some crucial step?

Here is a bigger version of the screenshot.