Update:
After contacting Samsung multiple times and after having been to 3 different "Samsung Service points", no one could help me and the only thing they could offer was that they would take our phones in and send them off to their technical specialists. Sadly, that is not on option for us, since we very much need our phones and can't just give them away for a minimum of three weeks.
Moreover, Samsung told me that we had been the ONLY people in The Netherlands that have come forward with this issue. They were pretty sure that Samsung was NOT planning on working on an update to fix the problem, since no one else had officially mentioned the problem.
However, I solved the problem as follows:
- Go to Settings - Personal - Cloud, make sure the bottom two options are turned OFF;
- Install QuickPic via Play Store;
- Go to Settings - Application Manager - All - Gallery and click "Force Stop" and then "Disable"
- Use QuickPic and never use or even mention Gallery again.
I am terribly disappointed in Samsung that they are making it so difficult to solve this problem. A simple messageboard like discussions.apple.com would have made a world of difference, in my opinion...