Edit : 14 July - these plug-ins have been removed. I just did a new install on Hostgator and they aren't there.
-------------------------------------
I thought I'd post this in case anyone else is experiencing the same problem. I have experienced this twice this week when working on clients' sites.
If you do a fresh install of Wordpress via Fantastico on Hostgator you will find a plug-in called WP Super Cache is automatically activated.
This plug-in seems to prevent your theme changes from displaying correctly on any browser.
You can see your changes saved in the admin area, but they will not be displayed by refreshing your browser (and I have tried this on 5 browsers)
Disabling this plug-in has cured this problem on two different sites on two different accounts, but both with Hostgator.