We had a similar situation. We have a .net application that was trying to use a print service that included the credentials for a secured WMS provided by an external source. Whenever we tried to use the print service, we received the 400 error. The only thing we needed to do at the end of the day to get it to work was to log into our ArcGIS for server machine using the ArcGIS Server account credentials and connect to the internet. ESRI suggested that when you log-in as the ArcGIS Server account for the first time, proxy settings are populated to it and the ArcGIS for Server can then access internet to connect to the external WMS service.
... View more