We often see those errors when permissions are incorrect or there is a firewall issue. Can I ask if you're using Database users or Active Directory users? If the latter, then when you are publishing it is 'you' that is connected to the database. When you publish you are in effect asking the ArcGIS Server (under a windows service account, i.e. 'not you') to connect to the database. Even though the server validates with the database, showing high-level connectivity, it does not confirm that it can access each feature class. You may need to check/change some permissions so that the ArcGIS Server 'service account' has the appropriate permissions to read from SQL.
Scott Tansley
https://www.linkedin.com/in/scotttansley/