I'm seeing similar problems on my Toshiba Portege 7200. Feels like my P3/600 has been replaced by a Pentium/75. After reading bug #284356, I tried upgrading to {kernel-image-,kernel-pcmcia-}2.4.27-2-686 (from sid), but I still see the extreme slowness problem.
Jason