A lot of DSL modems actually have routing functionality that interferes with your actual router. They tend to use a PPOE setup, which means you have to tell your modem to not do PPOE and use the settings that it had to tell your router it's a PPOE connection, complete with the login user/pass and external IP address the modem was getting. I know that sounds complex, so maybe just google on that subject with some keywords and you'll likely find the steps for it.
I've never had positive results with Windows registry cleaners. Either it made no difference or something got screwed up and I to do a system restore. It's quite a bit more work, but I'd recommend doing a backup, format, and clean install.