Serial ports are 25 pin. Actually, only 9 are used, so its not a problem getting an adaptor. Many times, the cables are not the right ones. I have seen, over the years, cables that apear to be correct, plug right in, and will not work. The reason is, most of the times there is a crossover. IE, what is a send on one side, must be a recieve on the other.
Modem drivers also must be correct. Sometimes drivers are not universal.
I am not a linix expert, but I would look into drivers and the cable. If it is not the original cable that is where I would start.
Also, your ISP probably is not familiar with that type of modem, hence thats why they are not helpful.