I've run Debian (2.0 through 3.0) on a computer with 133MHz and 16MB of RAM. It certanly was never quick, but it has been quite usable for my intentions. It ran X a bit slowly, but it was still usable.