NextGen plugin check failing, why?

The latest release updates the jquery and some plugins had issues with that, you can always upload the older version in the wp-includes directory.

I took a sneak peek in the code and the following snippet should be the culprit.

function ngg_ajax_test_head_footer() {

// Build the url to call, NOTE: uses home_url and thus requires WordPress 3.0
$url = add_query_arg( array( 'test-head' => '', 'test-footer' => '' ), home_url() );
// Perform the HTTP GET ignoring SSL errors
$response = wp_remote_get( $url, array( 'sslverify' => false ) );
// Grab the response code and make sure the request was sucessful
$code = (int) wp_remote_retrieve_response_code( $response );
if ( $code == 200 ) {
    global $head_footer_errors;
    $head_footer_errors = array();

    // Strip all tabs, line feeds, carriage returns and spaces
    $html = preg_replace( '/[\t\r\n\s]/', '', wp_remote_retrieve_body( $response ) );

    // Check to see if we found the existence of wp_head
    if ( ! strstr( $html, '<!--wp_head-->' ) )
        die('Missing the call to <?php wp_head(); ?> in your theme');
    // Check to see if we found the existence of wp_footer
    if ( ! strstr( $html, '<!--wp_footer-->' ) )
        die('Missing the call to <?php wp_footer(); ?> in your theme');
}
die('success');

This snippet loads your homepage body and checks if the wp_head and wp_footer are there. As you said you added these so that shouldnt be the problem. What I find strange is that you are missing a part of the die message, the wp_footer or wp_header parts.

As far as i can Tell it looks for < ! – – wp_head – – > (the comment) and not the actual code, the comments dont seem to be shown in your code did you add those?