Restoring a new iPhone via iCloud post-setup?
Since this appears to be a defect in Apple's software with no non-hacky solution, I thought I would share how I worked around this issue to achieve semi-restoration:


Photos: I first imported my photos from my iCloud photostream to iPhoto using this tutorial. Then I went to iTunes --&gt; iPhone --&gt; Photos and checked "Sync Photos from iPhoto." Further, oddly enough, after linking iCloud to my iPhone again post-setup, a photo stream was synced with my phone, albeit missing a lot of photos. But iPhoto was able to load them all, so it didn't really matter.
Contacts: Luckily I had my contacts already synced with my Mac Contacts app. So to add my existing contacts all I had to do was go to iTunes --&gt; iPhone --&gt; Info and check "Sync Contacts."
Calendar: I use Google calendar, so this was as simple as setting up my email again. However, even if you relied on your iPhone calendar, I believe this issue can be resolved by going to iTunes --&gt; iPhone --&gt; Info and selecting "Sync Calendar."
Notes: Once I linked my iCloud to my phone post-setup, these notes automatically synced from the Notes Mac app. 


What I was unable to sync:


Messages. Unfortunate but not really that important.
Applications. But these can easily be re-downloaded.