I had the same issue - Here is how I fixed it
Hold the sleep button + the menu button for 10 sec, wait until the Apple logo comes up and let the phone start then plug it into the computer.
Seems when I opened the box and connected the iphone to the computer I did it too fast not letting the device start, i also got the following message:
"You have inserted a disk containing no volumes that Mac OS X can read. To use the unreadable volumes, click Initialize. To continue with the disk inserted, click Continue."
I hope this helps someone!