"The datasheet specifically says PSEN should not be tied to ground during power up."

Where does it say this? I couldn't find it.

The instructions that come with Atmel's demo board actually tell you to connect PSEN to ground then power up the board.