deleted photos still take up storage
I had this problem for a long time with my 16gb iPhone. After a lot of looking I discovered iExplore and this tip:

http://iexplorer-support.macroplant.com/customer/portal/articles/1325738-how-to-delete-all-photos-from-an-iphone-or-ipad

Essentially, Photos caches lots of files and due iOS bugs, the caches don't always get cleared up.

I used the solution on the above page and cleared up 2GB of space.