Our DSL link, provided by BSNL (aka World's crappiest broadband service), was down yesterday causing enormous hardship. However today when it came back up, I could connect it using Windows (yeah, we still have couple of spare laptops lying around) but not on Linux. It gave me errors like:
1. pppoe: Timeout waiting for PADO packets
2. LCP: timeout sending Config-Requests

All the while the lights (DSL, Power and LAN) were on indicating connectivity. I could also connect to the modem indicating that the connection was ok (think again!). I tried everything imaginable like re-running the adsl-setup to create a new connection after deleting the old one, directly used adsl-connect, restarted network, even rebooted. None of them helped.

Finally I did the obvious, pushed harder the LAN cable connecting the computer to the DSL. And then the connection was back up!

So in conclusion never forget the obvious, the first thing you should try is push / adjust the LAN cables to ensure proper connectivity. In my experience with networks, over 90% of the problems are due to cabling.