I use Ubuntu 6.06 on an 800MHz Celeron (going to upgrade some day),
and Xubuntu 8.04 on an 800MHz Celeron in a laptop. Both do have 256M
of RAM. Performance is adequate, but nothing to brag about. (my
primary machine is at 3GHz and 2G of RAM BTW)

I also have Xubuntu 8.04 running on a 450MHz AMD K6-2 with 256M of
RAM. Performance is a little slower, but it does work if you have
patience. I don't know if an Intel chip in the same speed range would
do as well, back in the day, I seem to remenber that AMD had a
signifigant performance per MHz reputation,