I have a similar problem with my wife's new iMac. It can't connect to App Store, and it can't send email to iCloud by iCloud. I finally got it sending mail from another mail server, but not iCloud. I'm pretty sure it has sojnething to do with something from her G5 that doesn't work in 10.8. I just haven't found and deleted the right one yet.
The Genius at the apple store nuked and repaved it, and set it up with MY info instead of hers, and it worked. I brought it home, and set her up, and restored her time machine, and it didn't work!