Just to know, do everyone use iCloud?
Maybe it's a backend problem that rise up when you restore something from iCloud.
I never used it on my 5s and no problem at the moment with 9.3
So you should try to disable icloud and restart the phone. Would be better restore the phone as new and disable immediatly icloud, making a backup with itunes first.
Just my opinion but would be great to know if is icloud related.
I use iCloud but have never restored from it