iCloud backup/restore - how to get the rest of my stuff (photo's)?
According to Apple overview of iCloud backup photos are only included in iCloud backups when iCloud Photo Library is not enabled.

Photos and videos on your iOS devices
However, if you turn on iCloud Photo Library on your iOS device (iOS 8.1 or later) or Mac (OS X v10.10.3 or later), your photos and videos are already stored in iCloud, so they aren’t included in your iCloud backup.

Photo's are always included in iTunes backups.

Photos already stored in the cloud, like My Photo Stream, and iCloud Photo Library

You should be able to restore your photos by making certain iCloud Photo Library is enabled on your new phone.
You can verify whether your photos are in iCloud by using a computer and browser and going to iCloud.com and logging in with your appleId and password and then clicking the photos icon.