Well thank you everyone for your wisdom! Khen1950fx, I used your code to find a shift(array) method that works. By adding a shift() to each traverse line one by one and checking the results, I found out what I think the issue was. When a match is found, not only do we want to print the match by shifting the new array but we must also shift (but not print of course) the old array so that the indexes remain updated relative to one another. Then the other lines can just shift(old) or shift(new) accordingly. That must be why that one line was shifting twice. Here's Khen's augmented code:

#!/usr/bin/perl

use strict;
use warnings;
use CGI qw(:standard :html3);
use Algorithm::Diff qw(traverse_sequences);
use Text::Tabs;

open(OUTPUT, ">out.html");

my $old = '1 2 3 4 6 7 8';
my $new = '1 2 5 3 6 4 7 8';

my @old = split( /\s+/, $old );
my @new = split( /\s+/, $new );

my $style = <<EOS;
        PRE {
            margin-left: 24pt;
            font-size: 12pt;
            font-family: Courier, monospaced;
            white-space:pre
    }
        PRE.onlynew { color: red  }
        PRE.onlyold { color: blue }
EOS

print OUTPUT start_html(
    {
        -title => "$old vs $new",
        -style => { -code => $style }
    }
  ),
  h1(
    { -style => 'margin-left: 24pt' },
    span( { -style => 'color: red' }, $old ),
    span(" <i>vs.<i> "), span( { -style => 'color: blue' }, $new )
  ),
  "\n";

traverse_sequences(
    \@old,
    \@new,
    {
        MATCH     => \&match,
        DISCARD_A => \&only_old,
        DISCARD_B => \&only_new,
    }
);
print OUTPUT end_html;

sub match {
    print OUTPUT shift(@old), "\n";
    shift(@new);
}

sub only_old {
    print OUTPUT "<strong><font color=red>" . shift(@old) . "</font></
+strong>\n";
}

sub only_new {
    print OUTPUT "<strong><font color=blue>" . shift(@new) . "</font><
+/strong>\n";
}


close(OUTPUT);
[download]

The code above should create an HTML document that prints the new array; black font means nothing changed at that spot b/t old and new. blue font means that character was added in new at that spot, and red font means new does not have that character at that spot. Thanks again for everyone's generosity!