Custom header images won’t appear when set to random

Checked the code and it looks like the random header image functionality is happening inside get_header_image(). So the issue could be one of the following:

  1. Your elseif never gets executed. In other words, the if condition always evaluates to true and get_the_post_thumbnail() takes care of generating the image.
  2. Your theme does not support enabled for either custom-header, default-image, or both.

For a quick way to diagnose exactly what’s happening I would put debugging messages everywhere in your header.php to see what’s going on.

Here’s the source code of get_header_image() for reference.

function get_header_image() {
    $url = get_theme_mod( 'header_image', get_theme_support( 'custom-header', 'default-image' ) );

    if ( 'remove-header' == $url )
        return false;

    if ( is_random_header_image() )
        $url = get_random_header_image();

    return esc_url_raw( set_url_scheme( $url ) );
}

Edit: just found something. Try adding default-image param to your array for add_theme_support call, like so:

$custom_header_support = array(
    // The default image to use.
    // The %s is a placeholder for the theme template directory URI.
    'default-image' => '%s/images/headers/starkers.png',
    // The height and width of our custom header.
    'width' => 760,
    'height' => 280,
    // Don't support text inside the header image.
    'header-text' => false,
    // Callback for styling the header preview in the admin.
    'admin-head-callback' => '',
    'random-default' => true
);

Note: This link was super-useful in understanding which parameter is responsible for enabling random images in themes.