Back in the day, when I didnt have a job and only could do dialup - not broadband - I used wvdial. I just couldnt figure out pppd. I hoestly would never get it to work. Wvdia, otoh, simple to edit and made the scripts for me, and would connect at a good speed.
Try that. I am sure they still package that with most distros. RedHat, Slack, SuSE all did. Dunno about Debian and Mandrake. Never really used them back then.