Constant login prompts since changing Exchange 2013 virtual directory urls

I was having issues with my Exchange installation in that I was being prompted for SSL certificates for the wrong domain which I managed to resolve via this: post Outlook SSL error when connecting to new exchange 2013 installation. Now that I've updated all my internal / external Urls for the virtual directories some users are being prompted (Constantly) for their User / password which when entered doesn't seem to care and re-prompts seconds later. Everything works as it should when pressing cancel on the dialogue (as though it didn't need to authenticate) but I'm not sure what's causing it.

Another issue which might be related is when trying to activate Automatic Replies from Outlook 2013 a message comes up saying the Server is unavailable which is odd because we can receive / send mail etc.

The commands I ran to update the urls are:

Get-ActiveSyncVirtualDirectory -server EXCHANGE | Set-ActiveSyncVirtualDirectory -ExternalUrl 'https://mail.example.com/Microsoft-Server-ActiveSync' -InternalUrl 'https://mail.example.com/Microsoft-Server-ActiveSync'
Get-AutodiscoverVirtualDirectory -server EXCHANGE | Set-AutodiscoverVirtualDirectory -ExternalUrl 'https://mail.example.com/Autodiscover/Autodiscover.xml' -InternalUrl 'https://mail.example.com/Autodiscover/Autodiscover.xml'
Get-ECPVirtualDirectory -server EXCHANGE | Set-ECPVirtualDirectory -ExternalUrl 'https://mail.example.com/ECP' -InternalUrl 'https://mail.example.com/ECP'
Get-OabVirtualDirectory -server EXCHANGE | Set-OabVirtualDirectory -ExternalUrl 'https://mail.example.com/OAB' -InternalUrl 'https://mail.example.com/OAB'
Get-WebServicesVirtualDirectory -server EXCHANGE | Set-WebServicesVirtualDirectory -ExternalUrl 'https://mail.example.com/EWS/Exchange.asmx' -InternalUrl 'https://mail.example.com/EWS/Exchange.asmx'

Any ideas as to where to start looking into these issues as I'm a little baffled.

Edit: I've tried removing the account / profile and re-adding it (For outlook via Control Panel - Mail) again but it doesn't auto fill the information based on the domain account any more. Adding manually doesn't appear to work either now.

Results from the following:

Get-ClientAccessServer | FT Name,AutodiscoverServiceInternalUri,AutodiscoverServiceExternalUri -Autosize
    Name:           myserver
    InternalUri:    https://my.external.com/AutoDiscover/Autodiscover.xml (This is the same value I have in the internal and external Urls for the above commands I ran
    External:       

Get-OutlookAnywhere | FT Name,EXCHANGE -Autosize
    Name:       Rpc (Default Website)
    EXCHAGE:        

Get-OutlookProvider (3 lines returned)
    Name:   EXCH, EXPR and WEB  
    Server:     
    Cert:       
    TTL:    1 on all

Solution 1:

Check output for following cmdlets:

Get-ClientAccessServer | FT Name,AutodiscoverServiceInternalUri,AutodiscoverServiceExternalUri -Autosize

Get-OutlookAnywhere | FT Name,EXCHANGE -Autosize

Get-OutlookProvider

In addition, make sure the version of the Outlook client is properly patched to the minimum required Exchange version.

•Outlook 2013

•Outlook 2010 SP1 with November 2012 Cumulative Update ( available from http://support.microsoft.com/kb/2687623 )

•Outlook 2007 SP3 with November 2012 Cumulative Update ( available from http://support.microsoft.com/kb/2687404 )

•Entourage 2008 for Mac, Web Services Edition

•Outlook for Mac 2011