Finalmente consegui configurar o pppd para iniciar no boot.

O truque estava em colocar isso no arquivo /etc/network/interfaces:
pre-up /sbin/ifconfig eth0 up

Outra coisa, para evitar que a conexão ficasse caindo, eu comentei as seguintes linhas:
# The primary network interface
#allow-hotplug eth0
#iface eth0 inet dhcp

Para referência: Debian etch rodando speedy modem.