I have had a few headaches with the linux + winmodem equation too. On my own machine the solution was to buy an external serial-port modem. The setup from there was quite straightforward or at least as straightforward as anything is under Linux.
In a mindless fit of bravado, I made the mistake of offering to install Suse Linux 10 on the home PC of a workmate. It turned out that his machine had a winmodem fitted, and one that linux just didn´t want to know about. So we got the PC shop to change his winmodem for something linux-compatible. Trouble was, that version of Suse Linux came without any non-GPL licensed bits, including drivers for modems that had worked on earlier releases of Suse. After much downloading and installing, we were forced to admit defeat. None of the driver packages for that modem would compile cleanly.
At this point we gave up. Soon after, my friend upgraded to ADSL and getting Suse 10 to work with that was simple and painless.
