Mein Problem ist so weit unter http://ubuntuforums.org/showthread.php?t=1920561 beschrieben.

Ich habe den Server quasi identisch zu dem vorherigen installiert. Der alte Server ist ein Ubuntu 11.10. Dort funktioniert alles problemlos. Vom neuen Server von der Console aus kann ich normal pingen; das klappt. Auch die anderen internen Netze kann ich erreichen. Nur von Clients kann ich nichts erreichen.

Die IP Tables scheinen aber korrekt zu sein. Denn auch die Interface heißen alle gleich. Ich hoffe, dass sich das Problem lösen lässt.