Windows Vista Can't connect to the internet with any program but IE

I can't seem to get any of my installed programs to access the internet. Windows Media Player, ITunes, Firefox, Veoh Web Player all have permission, but whenever I try to, say, access the Music Store through Windows Media Player I get an error message stating that I cannot access the internet. This is true for all above programs (plus a few p2p programs). I've tried uninstalling, reinstalling, booting in safe-mode (a wonderful experience that), shutting down the firewall, shutting off the anti-virus software to no avail. PLEASE HELP!!!