How do I create a custom role capability?

Remove what you add

First, please make sure that everything you add on activation also gets removed on uninstall. I got a short tutorial including example code for you.

Test with a small plugin:

I really don’t know much about MU, but as far as I can tell, the roles object is global across all blogs. Just try this little plugin and see what you can get:

<?php
/*
Plugin Name:    MU Roles check
Plugin URI:     https://github.com/franz-josef-kaiser/
Description:    Check roles during viewing a blog
Author:     Franz Josef Kaiser
Author URI:     https://plus.google.com/u/0/107110219316412982437
Version:        0.1
Text Domain:    murc
License:        GPL v2 - http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
*/

/**
 * Show the blog data and the role names in this blog
 * Also shows if the custom capability was successfully added, or displays n/a for the role
 * 
 * @return void
 */
function wpse35165_role_check()
{
    $blog = get_current_site();
    $custom_cap = 'name_of_your_custom_capability';

    $html = "<hr /><table>";
    $html .= "<caption>List roles in (Blog) {$blog->site_name} / ID#{$blog->id}</caption>"
    $html .= "<thead><tr><th>Role Name</th><th>Capabilties</th></tr></thead><tbody>";
    foreach ( $GLOBALS['wp_roles'] as $name => $role_obj )
    {
        $cap = in_array( $custom_cap, $role_obj->caps ) ? $custom_cap : 'n/a';
        $cap = $cap OR in_array( $custom_cap, $role_obj->allcaps ) ? $custom_cap : 'n/a';
        $html .= "<tr><td>{$name}</td><td>{$cap}</td></tr>";
    }
    $html .= '</tbody></table>';

    print $html;
}
add_action( 'shutdown', 'wpse35165_role_check' );

Adding Capabilities

/**
 * Add the capability to the role objects
 * Should be in your activation function and done before you inspect with your plugin
 * 
 * @return void
 */
function wpse35165_add_cap()
{
    $custom_cap = 'name_of_your_custom_capability';
    $min_cap    = 'the_minimum_required_built_in_cap'; // Check "Roles and objects table in codex!
    $grant      = true; 

    foreach ( $GLOBALS['wp_roles'] as $role_obj )
    {
        if ( 
            ! $role_obj->has_cap( $custom_cap ) 
            AND $role_obj->has_cap( $min_cap )
        )
            $role_obj->add_cap( $custom_cap, $grant );
    }
}

Note: You can add the capability to the role without granting access to it – just set the second argument $grant = false;. This allows whitelisting single users with simply adding the cap including the last argument as true.