It would be nice to include built in support for PPPoE in the next version of LinuxMCE. To get it working on my machine, i had to disable the built in firewall and execute the following to get internet sharing to work:
iptables -t nat -A POSTROUTING -j MASQUERADE
Hindsight tells me i could of avoided a lot of pain by just modifying the device in the database like the wiki says, but it shouldn't be this hard to set up something so simple.