I recently upgraded from my iPhone 4S to an iPhone 5. I've been using iCloud for backing up my iOS devices for the past year, so I was somewhat familiar with it.
The first time I used iCloud to restore my iPhone data, in March, it didn't work well – actually, I gave up on trying to recover my camera roll with 12,000+ photos since it was already backed up on my desktop. It was just taking too long.
For my iPhone 5 restore, I waited it out. It took about 60 hours to recover my 30 GBs of backups stored on iCloud. It seemed as if each photo took about 10 seconds to restore. Of course, there were about 8-12 hours in there when I wasn't on WiFi and the iCloud recovery process was paused. So, let's call it 50 hours.
Why so long? Because it requires a lot of time to download that much data from iCloud, regardless of how big the pipe is (bandwidth) on your end. Unlike iTunes movies and music downloads, which happen in a jiffy, iCloud restores do not gain any benefit from content deliver networks (CDNs) such as Akamai or Amazon's CloudFront. A CDN will cache data, like movies, on servers that are as close to you as possible. That way the bits are only traveling, say, 100 miles, instead of thousands of miles. Less hops means faster delivery.
Once the iCloud restore was complete my iPhone then downloaded my apps, music, movies directly from the iTunes store, which did benefit from a CDN. Rather than store this information in my own iCloud storage Apple just keeps it on their servers since this information isn't unique. My last step was to resync with iPhoto to recover my photo albums – after all, iCloud only backs up your camera roll.
In the end, I didn't lose anything, it just took a very long time. For my next iPhone upgrade, I will backup my data via iTunes on my computer. Just keep in mind... if you have a 64 GB iPhone, you should make sure that you have at least 64GB free on your computer before trying to back it up.