I get the same error. I have an mxd with 1 featureclass and 3 related tables. The FC and 2 of the tables can be published, but the 3rd table gives the error "The StandaloneTable:'MyTable' in Map:'Layers' is invalid. The base table definition string "MYDATABASE.DBO.MyTable" is invalid. Failure to access the DBMS server."
The FC and the table are created by a script, so I assume that the privileges are the same for all of them. I can't really find any other difference between the tables.
10.1 SP 1 is already installed, so that cannot be the reason. I Also re-ran the "Configure ArcGIS Server account tool", but that didn't help either.
Other than the error above, the logs don't show anything suspicious (loglevel is set to DEBUG)
Any ideas?
EDIT: I found out what was going wrong. On the server, I opened the generated msd file (rename to .zip), and extracted layers.xml. Inspecting the WorkspaceConnectionString values revealed that one of the tables still pointed to the database on my development machine.
Unfortunately it is no longer possible to publish an msd, so what I had to do was, instead of publishing the service, create a service definition (sd file). Renaming that to .7z allowed me to open it, and extract the included msd. Rename that to .zip, extract and alter layers.xml, and then repack/rename everything to the original values.
The modified sd file could now be published.