It's kind of silly, but I am going to answer my own question here, in case anyone else runs into this problem, hopefully a super-search will get them to here.

Well, I finally managed to find a solution, which was to replace this line:

push @stack_trace, [ (caller($i))[0 .. 3] ] while caller(++$i);  
[download]

with these lines:

    {
        package DB;
        my $i = 0;            
        my @c;
        while (@c = caller($i++)) {
            next if $c[3] =~ /.*?\:\:throw/;
            push @stack_trace, [ @c[0 .. 7] ];        
        }
    }
[download]

For whatever reason, this needed to be called through the DB package to work under Devel::Cover, but the relationship between caller and DB are well known, so that was fine. The stack trace information gathering works the same, but since Devel::Cover seems to be messing with the index of the call stack the best way to was to capture more than I usually do, and to ignore the stack frames which came from my throw routine. This now passes both make test and Devel::Cover runs.

I am still trying to figure out what the real reason behind this all is, and I am planning to examine it deeper so I can submit a bug report as well. Any thoughts, comments or suggestions are still welcome.