I've been having the same problem for 2 weeks now. I tried searching online for a solution but turned up empty handed. According to Apple support its a problem with my ISP but when i try the connection with a windows laptop it works fine.
Its killing me because i havent been able to connect to the itunes store with my new imac and having to resort to windows for my podcasts is almost like a slap acroos the face - i made the switch and promised never to use windows again.
Btw, i also bought a new ipod but cant register it cause of the same bloody problem.