Outlook client free/busy not showing

I've got an odd problem.

I got my PC reimaged, and now it won't connect properly to the autodiscover service. I cannot see free/busy information, cannot set my out of office, and don't get tooltips about other people who have out of office on when I am emailing them.

If I run the "Test email autoconfiguration" tool, it fails.

All of that used to work before my PC was reimaged. Furthermore, if I log in to another PC (same OS, Win7) it does all work.

So I think the problem is specific to my PC, and not a problem with our Exchange setup.

If I browse to the url http://mail.mydomain/autodiscover/autodiscover.xml I get a 403 error. Doing the above on the other PC works.

Weirdly, if I browse to https://mail.mydomain/autodiscover/autodiscover.xml on the PC with the problem it works OK.

So there's something configured wrong on my PC, but I don't know what. Maybe it's not passing my credentials properly. Other sites that rely on my Windows credentials are working OK, so it's passing them correctly sometimes. Any ideas, before I get them to reimage my PC again?

Thanks

When I run Test mail autoconfiguration, on the Results tab I get:

Autoconfiguration has started, this may take up to a minute
Autoconfiguration was unable to determine your settings!

The log is:

SMTP=my.email@my.domain
Attempting URL httpx://mail.my.domain/autodiscover/autodiscover.xml found through SCP
Autodiscover to httpx://mail.my.domain/autodiscover/autodiscover.xml starting
GetLastError=0; httpStatus=403
Autodiscover request completed with http status code 403
Autodiscover to httpx://mail.my.domain/autodiscover/autodiscover.xml failed (0x80004005)
Autodiscover to httpsx://mail.my.domain/autodiscover/autodiscover.xml starting 
GetLastError=12007; httpStatus=0
Autodiscover to httpsx://mail.my.domain/autodiscover/autodiscover.xml failed (0x800C8203)
Autodiscover to httpsx://autodiscover.my.domain/autodiscover/autodiscover.xml starting 
GetLastError=12007; httpStatus=0
Autodiscover to httpsx://autodiscover.my.domain/autodiscover/autodiscover.xml failed (0x800C8203)
Local autodiscover for my.domain starting
Local autodiscover for my.domain failed (0x8004010F)
Redirect check to httpx://autodiscover.my.domain/autodiscover/autodiscover.xml starting    Redirect check to httpx://autodiscover.my.domain/autodiscover/autodiscover.xml starting
Srv Record lookup for httpx://my.domain starting
Srv Record lookup for my.domain Failed (0x8004010F)

Note I had to change http to httpx and https to httpsx to allow it to post.