File exceeds upload_max_filesize, despite max filesize being large enough

Apparently there’s an upload_size_limit filter in WordPress. To check what your site’s upload limit is set to, add this to your theme’s functions.php:

add_action( 'shutdown', 'wpse115322_upload_sizes', 99 );
function wpse115322_upload_sizes() {
    $size = wp_max_upload_size();
    $kb = $size/1024;
    $mb = $size/(1024*1024);
    echo( "$kb KB / $mb MB<br />\n" );
}

That’ll print your site’s actual max file size at the bottom of every page. If it’s less than you anticipated, it could be that a plugin or your theme has set it low. Try disabling all plugins, then turn them on one by one till you find the culprit. If it’s not a plugin, try switching to a default theme (Twenty Ten/Eleven/Twelve/Thirteen).

Reference

wp_max_upload_size() (The filter upload_size_limit is mentioned in the source)