1) have you viewed the template via a different browser, ie you are actually viewing the catalog side of the store NOT the dummy preview image of the template (sorry but i dealt with someone doing that and it was pretty similar to what you described)
2) What version of PHP and MYSQL are you using,
3) after changing the template to use, do the reset layout boxes thingie
4) after changing the template does it actually show as using that template on the templates page BEFORE you leave the page to do other things?
5) Is anything showing in your /logs/ folder, if there are errors they should be listed here