At the moment the host is saying:
I've checked the headers of your site and the cache is disabled.
The server is configured correctly, I've just added the logo URL and it seems to have worked fine and the settings have stuck.
However, the settings have not stuck. He says he checked a couple of hours after changing the logo and it was still there but it isn't and I can't get it to stick. So I've batted it back to them.
I'll keep updating this thread just in case someone else experiences the same problem and it might save them some time, although it does appear that this is a problem that's unique to me. Lucky me!