Make a manual backup to your computer, erase your iPhone (settings and content), set it up as a new iPhone and restore from the backup.
For whatever reason Apple decided to leave deleted photos as invisible but space occupying crap on iOS devices and the only method that really helps (at least in many cases) is to erase and to restore. I've done this on several iPhones/iPads and it always worked.