Dang, you're right - I checked again on my N800 after a fresh boot and launching xmms, with cat /proc/cpuinfo. Indeed it's at 398bogomips (400MHz). Maybe the CPU speed had gotten stuck earlier after launching and closing Media Player, I hear that happens sometimes.
However, CPU usage with xmms could stand to be better - while decoding the same 160kbit/s Ogg file, xmms takes about 20% (all visualization disabled, minimized) while mplayer uses less than 10%. Doh!
Still, xmms's interface is so awesome (seriously) that I'll take it, warts and all.
XMMS leaves my cpu at 400MHz (n810)
BTW don't use Alsa output - it's buggy.