What you done so far:
Your computer was having problems.
You formatted the drive and re-installed Windows XP (sp2).
After the format and re-install of XP all was well with the computer but you could not connect to the Internet.
When trying to connect to Internet you got the dun error 691.
You have worked through the KB 310431.
You then checked and tested your password and user name on another computer, where it worked fine.
When you tested the password and user name on another computer you used your cell to make the connection there by testing it as well and it worked fine.
You have tried uninstalling/reinstalling the modem. Not sure what you mean. Does your computer have an internal modem that you connect to your cell phone that you are physically plugging and unplugging, or do you have a cellular modem device supplied by Verizon that you are physically plugging and unplugging when you say ?You have tried uninstalling/reinstalling?? Do you hear the old dun noise or is it just get only the error code? Can you use your computer as a phone? If so, do you get a dial tone? All these questions are leading to, could you just have a bad jack/connection point on your computer causing this problem? Also, I once was having a problem with a dun that turned out to be a bad key on the keyboard. I typed in the password correctly but the bad key messed it up so I could not get the connection to work and I could not see the password was being typed in wrong because of those stars that come up as you type passwords. I was just suggesting these 2 items (bad jack, bad key) because you said you tried everything and so I offer them as possible things that might have been overlooked due to their nature.
Is it possible that your computer has an IP address that is incorrect and needs to be released and then renewed? If it is a cellular modem device supplied by Verizon can you call their tech support? Tech support always seems to want to cycle the IP addresses.
That is all I have, sorry I can?t think of anything else, hope it helps.