Reinstalling probably isn't going to help things, each time it was different probably because you selected different options in the package utility programs.
I just installed debian tonight and had something similar to what you're describing.
I was trying to use wvdial, and wvdial wouldn't find the modem. Then after I solved that problem, it would connect but internet programs like lynx had no access; it wouldnt' resolve the host. Then after a few common sense solutions I was able to get connected and now the system is updating the x-window system (for some reason X doesn't detect the mouse so i'm upgrading it).
This is what I did to solve the wvdial and host problems:
1. Ran base-config and the updater agent probed for my modem and found it then I killed base config.
2. made a symbollic link to /dev/modem from /dev/ttyS0
3. made /etc/wvdial.conf
Modem = /dev/ttyS2
Baud = 57600
Init = ATZ
Init2 = AT S11=50
Phone = 555-4242
Username = apenwarr
Password = my-password
Phone = 555-4243
Init3 = ATM0
Dial Command = ATDT
edited it to meet my requirements.
4. Turned off my ethernet card
5. Ran "wvdial &", it connects, and allows me to surf the internet.
Kppp usually resolves host problems on its own, that is what is different about your problem. You might need to shut the ethernet card, if that doesn't work, try wvdial and see if you can get connected.