How can I change Max Embed Size in WordPress 3.5?

See the function wp_embed_defaults() in wp-includes/media.php:

function wp_embed_defaults() {
    if ( ! empty( $GLOBALS['content_width'] ) )
        $width = (int) $GLOBALS['content_width'];

    if ( empty( $width ) )
        $width = 500;

    $height = min( ceil( $width * 1.5 ), 1000 );

    return apply_filters( 'embed_defaults', compact( 'width', 'height' ) );
}

To change these values filter embed_defaults:

add_filter( 'embed_defaults', 'wpse_76102_new_embed_size' );

function wpse_76102_new_embed_size()
{
    // adjust these pixel values to your needs
    return array( 'width' => 1000, 'height' => 600 );
}