So, ich hab jetzt mit Ubuntu 12.04 und dem PDF betrachter etwas rumgespielt und festgestellt, dass es ein Bug ist, wenn A4 AutoDuplex nicht automatisch ausgewählt ist.
Dann muss man folgendermaßen vorgehen:
Datei -> Drucken -> den Drucker auswählen der Duplex drucken soll -> Seite einrichten -> bei Eigenschaften "A4 AutoDuplex" einstellen. -> Allgemein -> anderen Drucker auswählen -> den Drucker auswählen der Duplex drucken soll.
Nun kann man alles beliebig einstellen, auch die Einstelllung A4 AutoDuplex kann z.B. auf A4 Borderless umgestellt werden.
Das ist kein Problem, nun ist Beidseitig unter "Seite einrichten" nicht mehr ausgegraut.