Ho controllato sul sito della sun, in effetti il modo per impostare il frame a tutto schermo e' quello che ti ho detto. Il problema che hai tu e' che quando cerchi di "massimizzare" il frame, questo non e' ancora stato "validato".
Per validare un frame bisogna chiamare show(), pack() o setVisible().
Se prima lo visualizzi e poi lo ingrandisci funziona ma puo' sembrare fastidioso, un'alternativa e' quella di chiamare pack() prima di setExtendedState() e poi setVisible().
Cosi' funziona correttamente.
Per quanto riguarda linux, niente da fare, e' un bug ancora aperto