Do they have call answering ? I know this used to cause problems a few years ago with some US robotics modems .... as soon as the modem was turned on it would effectively "pick up" the line and if a number wasn't dialed in time call answering would cut in and a no dialtone msg would come up.
You can also try hyperterminal to test the line and modem, open hypertrm give the session any name, select the com port the modem is connected to or the modem itself but don't enter a number, ok the next screen or 2 until you get a blank white page then do the following hitting enter after each one
at
ate1 - this turns on screen echo
atz - this resets the modem
adtd 1891.... or whatever the isp number is.
If you get a no carrier message or no dialtone then there is a problem with it seeing the modem/phone line.