Well, It looks like I have resolved the issue and found the root cause. The issue was due to the browser sending the requested URL via our proxy server and the proxy server changing the authentication headers before they reach the web server. This was only occuring when using the FQDN as we had the bypass local addresses turned on and therefore when using the Netbios name, it would not go through the proxy.
Turning the proxy settings off in IE, I can connect to the application catalog using the FQDN. Putting in an exception for the servers FQDN into the IE proxy settings resolves the iss