Well I'm a complete newbie so just my expirience:
I had that probllem when I was trying to log on to my provider with PAP (or whatever) authentication and he was using CHAP authentication.
That was on Mandrake and kppp as a dialer.
Maybe it's something like that.