The following seems to me to be linear-time ^*, as opposed to your algorithm, which looks quadratic (but eye-balling running times is notoriously unreliable, especially for me!):

my @runs;
my $pos = 0;
my $b = $a;
my $c = lc substr $b, 0, 1, '';
my $next;
while ( $b ) {
    my $start = $pos;
    1 while ++$pos and ( $next = lc substr $b, 0, 1, '' ) eq $c;
    for my $i ( $start .. $pos - $n ) {
        push @runs, substr $a, $i, $n;
    }
    $c = $next;
}
[download]

UPDATE: Wow, I completely misread! My original version just printed out all runs of a repeated character. I've fixed it now.
^* At the expense of not using regexes, which you specifically requested. Oh, well. Is there a reason that you prefer to use them?
UPDATE 2: Whoops, I was eating one character too many each pass through the loop.
UPDATE 3: OK, now I've actually tested it. Sorry about that. :-)