I don't think there are any good reasons why an XC3S500E wouldn't work, the board layout would just have to be changed a bit. It has more available I/O, more capacity and it's cheaper.
Personally, I don't think we should change too much of the original design before the first board run is ordered (or else, it'll never be finished), but changing the FPGA is no bad idea at all. In addition to the things already mentioned, it's newer too(AFAIK), and therefore less likely to get obsoleted soon.
Having to redesign the board and testing the new design could mean that we would have to wait a bit longer for the final board, but getting a board with a higher capacity FPGA and more I/O at a lower price is attractive.
PSRAM seems perfect for this, the only problem is, it's only available in BGA. At least it was the last time I checked. Too bad, as it's damn cheap and available in relatively large sizes. Some sort of dynamic RAM would probably be a good idea for the future, provided we could find a solution that didn't tie up too many FPGA pins, but implementing something like this in the core before the first board run would take a lot of time, so I think we should stick with one 1Mx16 SRAM chip for now.
Anders M.