What kind of modem is it? Brand and model number. IE "US Robotics Sportster 56K"
I almost feel the need to appologize for making you look at this grossly bloated HOWTO, but you may fix your problem, or more importantly, learn something from it.
http://www.ibiblio.org/pub/Linux/docs/HOWTO/Modem-HOWTO
Long ago when I was still on dialup, I never would have dreamed of using 460800 in my options file. I recall going no higher than 131070 or whatever the closest number is to that, I don't recall exactly.
Hope this helps. Get back to me on what kind of modem you use and I might be able to conjure a modem string from memory of my ISP tech support days.
G'luck.