My laptop dial up built in modem make is 'HD AUDIO SOFT DATA FAX MODEM with smart ICP'. I tried to configure in different Linux OS like Fedora core1, RedHat Linux Enterprise 4.0, Ubuntu 6.06 and now Kubuntu. When I query the modem it always shows the modem is busy. How to overcome this and make the modem work?

your modem is not really a modem, as you stated it is a soft modem. If you are lucky, the manufacturer has released the code which will allow you to control it within linux. Many problems with the soft modems is that the manufacturers only release the code to control it for windows, leaving everything else without an option on how to control it/use it. Basically these modems are controlled by software and use the resources of the computer rather than hardware on the modem itself. Want more info, try reading the wiki on it: http://en.wikipedia.org/wiki/Winmodem

If windows is installed on this laptop, boot into and check out the details of the device (make/model) if not try the laptops makers site and see what they list, this will at least give you a starting point for what you should be looking for.
You may want to check out http://linmodems.org/ for some help on