Yeah, I fought that a number of years ago. You must either have a full hardware moden, usually external, or a driver that does the work a real modem would. Beware of controllerless modems. They are a step up from winmodems, but still need the computer to do some of the work. Perhaps you could port the Xandros driver to Ubuntu.
Check
http://www.linmodems.org/
When I finally bought a modem that worked with my computer, it didn't work with my phony company's switching equipment. At least half the time, it missed some digits and failed to connect.
Just before reaching the point of fire bombing the local phone company, I discovered VOIP. Now my computer happily and successfully shares its high speed cable connection withthe phone. Internet, local phone, and unlimited long distance including part of Europe runs me $76.mo.