I had similar prolem after updating to 3.8.
I could not delete any media, I could add, but could not delete.
Tried to add in wp-config.php
define('WP_DEBUG', true);
and what did I get.
DELETE FROM wp_options WHERE option_name = 'rewrite_rules'
Just added access for current database user to use DELETE sql command.
Solved my problem.
