Also die Lösung ist da: (für mich zumindest

)
Also da der Server meinem Kollegen gehört und er somit root Zugriff hat, habe ich ihm angewiesen, die deutschen locales mal zu installieren/generieren.
Das geht ganz einfach mit
dpkg-configure locales
Da de_DE.ISO-8859-1 auswählen und auf OK, dann fragt der nach Standard locale, da kann man auch das de_DE wählen und dann auf Beenden oder OK oder wie auch immer. Dann generiert der die Sprachdateien. Dann noch mal eben den Apache neustarten mit
/etc/init.d/apache restart
und schon gings. Natürlich alles als root.
Wenn eine Fehlermeldung kommt, dass keine locales installiert sind, dann ein
apt-get update
und dann
apt-get install locales
Viel Spass beim Nachmachen...
Gruß
Mokak