Um mês depois, e executando o Arch Linux, descobri o problema real e sua solução.
Meu Dell D600 não tem uma bateria e está funcionando apenas com energia do adaptador de CA. Quando o BIOS detecta que não há bateria instalada, ele reduz a CPU permanentemente para evitar sobrecarregar o adaptador de CA.
Se você quiser sobrescrever este comportamento, tudo o que você precisa fazer é adicionar processor.ignore_ppc=1
ao final do comando de inicialização do kernel (normalmente encontrado em sua configuração do GRUB). Então você pode usar o driver acpi_cpufreq para habilitar a escala de frequência da CPU corretamente.
Ou você pode optar por não ser barato e comprar uma bateria. Isso também resolveria o problema.