I am running Linux Mint based on 8.04 (and I will not give it up). I only ran
Gutsy Gibbon from the live CD in order to try again to configure PPPoE under it
and I succeeded with sudo pppoeconf in the terminal but it connects only if
roaming mode is disabled and the connection set to DHCP (in Network Manager). I
will retry the same under Debian Live Lenny and Kubuntu (which is nice but has a
useless KPPP program).
Under 8.04 and 8.10 the whole thing can be done by using the GUI of Network
Manager.

I am going to install Fluxbuntu this night (although it is torture) on another
hard disk and configure PPPoE under that one, also. It has the same networking
as Gutsy Gibbon.