You have to alias the postmeta table for the second value:

$querystr = "  
        SELECT $wpdb->posts.* 
        FROM $wpdb->posts, $wpdb->postmeta, $wpdb->postmeta AS mt1
        WHERE $wpdb->posts.ID = $wpdb->postmeta.post_id 

        AND $wpdb->postmeta.meta_key = 'key1'   
        AND $wpdb->postmeta.meta_value = 'value1'
        AND mt1.meta_key = 'key1'
        AND mt1.meta_value = 'value2'

        AND $wpdb->posts.post_status = 'publish' 
        AND $wpdb->posts.post_type = 'post'
        ORDER BY $wpdb->posts.post_date DESC
            ";

You can also do this now since 3.1 with a meta_query:

$args = array(
    'meta_query' => array(
        array(
            'key' => 'key1',
            'value' => 'value1',
            'compare' => '='
        ),
        array(
            'key' => 'key1',
            'value' => 'value2',
            'compare' => '='
        )
    )
);
$query = new WP_Query( $args );

You have to alias the postmeta table for the second value:

$querystr = "  
        SELECT $wpdb->posts.* 
        FROM $wpdb->posts, $wpdb->postmeta, $wpdb->postmeta AS mt1
        WHERE $wpdb->posts.ID = $wpdb->postmeta.post_id 
        AND $wpdb->posts.ID = $wpdp->mt1.post_id

        AND $wpdb->postmeta.meta_key = 'key1'   
        AND $wpdb->postmeta.meta_value = 'value1'
        AND mt1.meta_key = 'key1'
        AND mt1.meta_value = 'value2'

        AND $wpdb->posts.post_status = 'publish' 
        AND $wpdb->posts.post_type = 'post'
        ORDER BY $wpdb->posts.post_date DESC
            ";

You can also do this now since 3.1 with a meta_query:

$args = array(
    'meta_query' => array(
        array(
            'key' => 'key1',
            'value' => 'value1',
            'compare' => '='
        ),
        array(
            'key' => 'key1',
            'value' => 'value2',
            'compare' => '='
        )
    )
);
$query = new WP_Query( $args );