I have been sweating over the same problem all afternoon. I cannot get my spreadsheet to save a Legal page size in the Page Setup Dialog. When I quit Excel and save it, the next time I open the spreadsheet it has reverted to US Letter Borderless for some strange reason. I even clicked Save as Default in the dialog drop down and it doesn't help.
I'm very frustrated with this problem and would welcome suggestions. I have just upgraded to Lion so that may have something to do with it.