This might seem an out there suggestion, but we had a problem like this one when we reinstalled one of my brothers computers, turned out when we put the date in we were 5 years out and it upset everything. As soon as we changed the date we could connect to the net.
Is the date in your system correct?