I'd try some of the following things (in relevance order):
1.Restart ArcMap and try publishing again - the data store might not have been updated for the ArcMap session.
2.When adding the data from a SQL Server Express (under Database Servers), make sure your data path is identical to what you've registered the data store for. I.e., the ".\SQLExpress" is not the same as "servername\SQLExpress" when registering a data store - I remember having this problem myself. I never use the ".\" in the connections > use the machine name both when registering the data store and when establishing the connection to a SQL Server Express instance in the Database Servers section.
2a. Make sure as Sunil mentioned that the ArcGIS Server Account has permissions at least to read the data. Double-click Database Servers in the Catalog tree. Right-click the database server containing the geodatabase and click Permissions. Click Add User and add the ArcGIS Server account. Click OK. Double-click the same database server. Right-click the geodatabase, click Administration, then click Permissions. Click the ArcGIS Server account to select it and choose the level of permissions you want it to have.
3.Restart the ArcGIS Server Windows service.
4.Restart the machine.
Post back to let us know what has (if) helped.