If it is an error with the modem, it is most likely with the drivers, upgrading them might help, using a different modem would use different drivers, so it would help clear up one possible problem.
However the error points to a problem with Dial up Networking, probably Winsock. If you have not removed Dial up Networking and then reinstalled it, the problem will remain, just reinstalling doesn't seem to make any difference. If you do decide to do this, make sure you have a record of all settings in your DUN entries, like access numbers, server settings, etc.
Incidently what operating system are you using, earlier versions of Windows 95 benefit from upgrading DUN.