Ok, the ESRI folks and I have figured this out.
The symptoms:
Every time I would try to publish a map service from ArcMap, I would get an error. Checking into it, the underlying error was:
'User does not have permissions to access 'system/publishingtools.gpserver'. This would happen even though I was using the ArcGIS Manager account (the non-domain account used to log into Server Manager) when I would create my connection to the service. I have a Windows Domain user store, ArcGIS Server Built-in Role Store, GIS Server Authentication Tier (which I'm going to change), and ArcGIS Tokens ad the Authentication Mode. I have Admin and Publisher roles that contain my domain accounts.
The problem:
So after John O from ESRI (big thanks) had me install Fiddler and we looked through the more detailed messages, the error was that the token that was returned by the ArcGIS Manager Account was being denied. We took a close look at why this was happening, and it turned out that even the ArcGIS Manager account did not have permissions on the System services, though this may have been the result of me changing the security settings to use domain accounts (we're still looking into that part). Regardless, no users had permissions to access those system services such as system/publishingtools.gpserver. We checked this by logging into Manager as the ArcGIS Manager account, clicking Services > System, then clicking the lock icon on the System item (where you set the security settings for all system resources). We could see that the security was set to Private, and there were no groups in the Allowed Roles. Still, one would think that the Server Manager would have permissions....
The fix:
Once in System > Security settings, the settings were changed to Public, and a test service was published successfully from ArcMap. Then we went back in, and change the System > Security settings to Private, and added the Admin and Publisher ArcGIS Roles (which contained domain accounts). At this point, I am able to publish map services from ArcMap, as long as I create my ArcMap server connection using a domain account.
I hope this helps somebody else.