This information here is somewhat dated, but maybe it will give you a clue. Your symptoms sound quite famaliar, and are very similar to a common complaint in Corel Linux when it came out. Corel Linux used KPPP as its default dialer.
The problem is in the way KPPP and the default pppd program supplied with Debian is configured. KPPP will use SOME of the pppd config files, but not all. Specifically, it relies upon the /etc/ppp/options file, but will not use any of the /etc/ppp/options.XXXX files, nor does it use the "provider" constructs. KPPP will keep its config info in a separate file in your home directory. The standard pppd as supplied by Debian comes with a rather "generic" /etc/ppp/options file that includes the "AUTH" option. This option requires the remote computer to authenticate itself to your computer, and most ISPs will not do this, causing the link to break after this times out. This was the "problem" in using KPPP with Corel Linux. The "fix" was to edit the /etc/ppp/options file and change any "AUTH" entry to "NOAUTH". Several reported success with just commenting out this option, but I didn't have much luck with doing that here. Doing this edit will impair the security of your Debian box when acting as a "dial-in" ppp server, but if you don't use it in this manner nothing much will happen except KPPP "might" work then. This might be something you want to check out.... Cheers, -Don Spoon-
