Burlynurd, make sure that you have removed any and all PPPoE connection software from your computer, as well as removing any PPPoE settings in the Network settings. MacPOET, Enternet, etc. are examples of this connection software. If your ISP provided an "installation CD," it probably installed the software, perhaps without you even noticing it.

Running both hardware (the Linksys router) and software PPPoE connections is guaranteed to screw everything up. PPPoE requests from the software positively boggle the router and it sort of freaks out.