Nachdem ich keine wirkliche Lösung gefunden habe, habe ich in der gm_dynamics.css.php am Ende einfach die entsprechende class neue definiert:
Code:
#shop_logo{
                    background-image:url(backgrounds/bildwechselscript.php?".time().");
                    }
Mit dem Timestamp erzwinge ich jetzt den reloade des scripts und es wird nicht mehr gecached, somit wird auch der header immer neu definiert und die Weiterleitung funktioniert.
Etwas dirty, ich weiß.

Alle anderen Lösungen scheitern einfach daran, dass das Bildwechselscript selber gecacht wird und somit das Ergebnis = header-Weiterleitung immer die gleiche ist.