I had this problem as well and have determined that the problem is in icloud. If your photos have not been completed uploaded to icloud or vice versa from icloud to your device you will receive that error. It is possible that your phone may not be uploaded because of photo or video size etc and your device is trying to save your data. It will transfer directly when in wifi though. It can be because of data etc but without going through your settings there is no way to know for certain which is the problem. Here is the semi quick fix that worked for me.
Turn off "Icloud photo library" in settings>photos>remove from phone.
This will temporarily cause multiple if not all pictures to be removed from the device. DON'T PANICK! Those pictures that were removed from the phone have been uploaded to icloud and are not lost.
Now turn the icloud photo library back on (I had "Optimize Iphone Storage" set to On.)
Now unless you have a plan with unlimited data, your phone will pause until you are back on wifi but you can force it to begin without. If you elect to wait, simply login to wifi at your next available time and it will begin to redownload all photos. The error message will then subside and you can begin sharing again like normal.
Agreed it is a huge hassle that this happens but it is due to data usage and Apple programming your device to not allow excessive overage without consent. - Just my opinion. Good luck and hope this helps!