I wasn't able to reproduce the problem. Also, the script needed some changes to run under strict.

The word "tag" has a special meaning in the Tk domain. You aren't storing any tags in the @TAGS array, you're storing ids of the rectangles.

What about using a single tag for the background?

         $canvas->createRectangle(
             $i * $ps, $j * $ps,
             $i * $ps + $ps, $j * $ps + $ps,
             -fill    => $c,
             -outline => $c,
             -tags    => ['bg']);
      }
[download]

The erase routine can be now simplified to

sub erase{
    $canvas->delete('bg');
}
[download]

No need to store any tags/ids anywhere. That's usually the reason why to use the Canvas.

Update: I would also use tags for the lines, so you can easily raise them above the new background.

       $canvas->createLine($start_x, $start_y, $x1, $y1,
                           -width => 2,
                           -fill  => 'white',
                           -tags  => ['fg']);

# ...
# and after drawing the new background:

   $canvas->raise('fg', 'bg');
[download]