Still WIP on some fixes (tests are OK, code is somewhat broken...) 

Also, this fixes some inconsistencies in when / what exceptions are thrown between different storage backends.