Well, I don't think the Mozilla thing is your CPUs fault, Mozilla uses a slow as balls Java rendering engine as opposed to the native QuickDraw, it's their fault. It's even sluggish on a dual G4.
That 400Mhz thing sounds great, and indeed I would expect YDL or any other Linux to run fine on that with all the bellas and wistles. That is of course if you can get it to use the upgrade card.
The other thing that may be a problem is RAM and HD space. Your HD better be at least 10 Gigs to get good performance, and I would suggest 256 of RAM for KDE. GNOME seems to require less.
Also, because of the slow System bus on a performa, I can't be sure if the CPU card will indeed provide enugh kick. But it's speed is encuraging. Go for the install, let us know how it works.