...I've had this problem as well. For me, it's followed this pattern so far:
(1) dial in and connect to my ISP without troubles.
(2) Quit PPP Connect
(3) Dial in again, get LCP Failure
(4) Quit PPP Connect
(5) Delete the com.apple.pppconnect.plist file from
(you can do this with the finder without needing to be root or anything.)
(6) Open PPP Connect, reenter all your information (don't forget the DNS infos!)
In an effort to stave off the insanity, I've made a screen-shot of my PPP configuration with Grab, so I can copy it in easily.
The first time you connect, after entering the information fresh, no preferences file (.plist) is created. I believe it is created when you quit and the prefs are saved. Apparently, there must be some mismatch between the saving and the loading of the prefs, because the next time around, when the prefs are loaded from disk, instead of entered by hand, the connection doesn't work.
(* PowerBook G3/300 (Wallstreet II), 192 MB RAM, OS X on separate partition. *)