Dave's suggestion would seem unlikely unless you have recently added an extension or other device to the line. Do you know how near this limit the line was without the modem? I'm guessing but perhaps it was nearly on the limit. It's not impossible for another device on the line to be the cause of the problem. We had a faulty phone in my parents bedroom causing all sorts of wierd and wonderful problems.
One thing you could try is disconnecting every other device except the modem and then trying to dial up. If it is another device, you should then be able to sort it by a process of elimination.