Ono nejspíš záleží na konfiguraci kernelu, matně si pamatuju, že tam jsou pro tuhle věc tři volby- do 1GiB (s tím si ale nejsem jistej), do 4GiB a nad 4GiB (nějak tak to je). Možná má PAE nějaký vedlejší účinky, který by mohly např. na starších mašinách působit neplechu.
Debian by to mohl zvládnout, akorát nevím, jestli Lenny (chce to zkusit), u Sida a Squeezeho je to tutovka, tedy pokud si tam nainstaluješ bigmem kernel.