The behavior that you are encountering can occur if the Tableau Server refers to itself by one name, but users that connect and publishing workbooks refer to the Tableau Server by a different name. This can easily occur in SSL situations where the certificate Common Name is for a fully-qualified domain name.
The Tableau Server hostname can be set via tabadmin. Using tabadmin for this is covered in the Tableau Server Administrator Guide, available at the URL below, in the "Reconfiguring the Server" section (page 248 of the current manual):
For further troubleshooting, I am going to suggest creating a support case. Please be sure to include screen shots and server logs if you do.