Where has all my storage space gone?
I use DiskUsage for situations like this. It graphs the directory structure for you in a very pedagogical way to show you what directories (and subdirectories) that are taking up the most space. It literally solves situations like this in 15 seconds for me, because I'll see a big square with the text "Movies" or something on it, realizing I completely forgot I put an entire season of Wonders of the Universe on my device or something — or I'll se a folder with a name of an app that has long since been deleted with a bunch of useless cache :)

Try it out, I'm not sure how well it works on non-rooted devices but I think it should work on those as well, I don't think it does anything else than list directories and add their content size up.