Using various Pentium 4 computers with various distros I've tried to connect to the internet using an external modem. I'm currently using the same modem with a P3 computer & Ubuntu 6.06 to write this (so maybe no problem with the modem). Using my Compaq Evo d510 SFF (for example) I am able to configure the modem, hear the modem connect with my service provider & see that the browser is serching for an address but never connects properly - even after numerous re-trys. Usually the modem shuts down after a few minutes and the line is no longer busy. Sometimes connection starts to be made with the progress bar moving but the connection never completes. I've tried other P4 computers with the same modem but never been sucsessfull.

Pick a machine and a distro, and get back to us.

If you use Ubuntu - use the commandline to configure and connect.
The file you need to modify is /etc/wvdial.conf (or ~/.wvdial.conf)
The command is wvdial

Post the output.