I've upgraded CPG to v1.4.26 and that caused a problem with CSS not being used correctly. After a lot of poking around I narrowed the problem down to the Photo Shop plugin - when uninstalled CSS worked correctly. I then updated to plugin v1.4.1 (http://forum.coppermine-gallery.net/index.php/topic,57206.0.html) but this brought back the problem.
Is it possible that the updated/downloaded plugin was corrupt?
Are you running any other plugins that have not yet been updated?
If I'm following correctly, you updated CPG which rendered Photo Shop outdated and caused (you believe) the CSS output issue. You then uninstalled PS and the CSS problem disappeared. You then downloaded the latest version of PS, installed it, and once again resulted in the damaged output issue.
This would lead one to believe that the problem is Photo Shop specific, but that's not always the case, especially with other plugins installed. It could be a plugin conflict. It could be a server issue (check php compatibility; check phpinfo), It could be bad javascript. It could be a compromised web space. It could be a few different things.
I guess, my next step would be to download a fresh copy of the plugin, completely purge the current plugin from the directory tree after uninstall, deactivate all other plugins (if applicable) and go from there. I might even download a fresh copy of CPG itself.
Or... maybe there's a legitimate bug? Perhaps post to Stramm's board? Surround yourself with others who utilize that particular plugin and have experience with it. I'm out of ideas :-)