I had the seemingly-stuck "Restoring from iCloud Backup" lock screen message, and after 8 days it has finally completed without my doing anything (at least, without doing anything that worked; I tried a bunch of things). I had resisted doing anything to stop the restore because there is no easy way to see that ALL the data has finished restoring, or to see what the restore is doing, exactly, and I didn't want to lose any data. After several days I noticed that by looking at Settings > General > Usage > Manage Storage, I could see that the space taken up by my photos was slowly increasing. I started taking a screenshot of the data information each night, and confirming in the morning that the numbers were continuing to rise. Moreover, I could see that additional "new" photos (actually very old ones that just hadn't restored yet) were continuing to appear in the Recently Added album in the Photos app as recently as today. Finally, late this morning, 8 days after beginning the restore, the lock screen message has disappeared and I am able to backup the phone and upgrade to iOS 8.1 without interrupting anything. In my case, the photo library seems to have been the last to finish. I have 22 GB of photos on the phone, and my internet connection is not all that fast. Had I interrupted the restore (either explicitly, or by forcing a new backup to iTunes and restoring to that) I would have lost some of these pictures, which I found unacceptable. So, if you can stand it, I would recommend patience. I'm not saying nobody's phone is stuck, but mine wasn't. It just hadn't finished yet.
I think iOS 8 is the first version that gives you a lock screen message to say that a restore is ongoing. In the past, my restores may have taken just as long, but I didn't notice. I hope in future Apple can add some progress information (percent restored, perhaps); as things stand we are left to wait and to have faith. In my case, faith turned out to be justified, but it wasn't easy to maintain.
d.