Perhaps you can know the problems by looking at the ppp's log at /var/log/ppp.log.
You can also have ppp debugged by including the debug option in /etc/ppp/options and re-run ppp then read /var/log/ppp-debug.log.
btw are you always running ppp in kde? have you tried running it in console? if you want to run it in console you can use wvdial for that:
http://freshmeat.net/projects/wvdial/
Of what I'm thinking here is that maybe you failed to compile the proper modules in your kernel or else the ppp utility is having problems working with the kernel. Try to look at your kernel's config again and/or update your ppp utility.
Also check that your kernel is using the proper modules not the old ones. BTW do you use an initrd when booting?
Whatever you do just base it from the logs.