How many photos would you say you have on your device? Rough estimate? It's late and it was an early morning, but I'm thinking maybe you haven't deleted enough to make a dent?
If you are trying to clear space, what about syncing with your computer and deleting the images from your iPhone. Get things squared away and then sync the photos that matter most back to your iPhone.