So it was just a fluke, the day when Ubuntu suddenly started running smoothly again on my old HP laptop after I started it without network connection. I fiddled for some time to make it work, eventually downloaded Kubunt, and its music player Amarok does not stutter easily (as, with less than 100% load) the way the rest do. This, unfortunately, is because it is a resource hog. Other things slow down when using it. So now I am aiming for something more drastic.
Currently downloading Xubuntu 8.10 desktop CD ISO. I intend to delete the whole Ubuntu partition (having backed up that home folder already) and replace it with a fresh install. I will try Xubuntu first because it is a version of Ubuntu made for older, weaker machines. It system requirements are much less. Actually they are much less than what I have, so it seems like a bit of overkill, or underkill. And it uses the same underlying kernel, so chances are it won't make a difference. But perhaps a fresh install will fix something that has become stuck in a wrong way, who knows.
If that fails, I would like to try an older install of Ubuntu, from before the slowness. 6.06 (Dapper Drake) worked well enough, and is a Long Term Support, still supported until June 2009, so it should be available. I believe 7.04 Feisty Fawn also worked, possibly also 7.10 Gutsy Gibbon despite the new Compiz environment. (I use Metacity anyway so that's not it.) I am actually not sure if the slowing happened during 7.10 or sometime during 7.04, it has definitely been slow for the two last releases (8.04 and 8.10, the numbers referring to year and month respectively).
I've also heard good things about Linux Mint, and it has a new version out now. There is a warning that install may hang with less than 512 MB RAM though, and the old HP has that minus 65MB that are reserved for the video chip.