It sounds like the immediate cause of the problem is unescaped regex metacharacters. You can fix that with quotemeta or /\Q$foo\E/ in the regex.

From your description of the problem, it sounds like the eq operator might do better than a regex.

Your algorithm seems to be quadratic. You would speed matters by taking each line, or an md5 digest of it, as a hash key. You would then only need to check existence of a key to find like lines.

Update: Here is an example:

my %filehash;
{
    open my $fh, '<', '/path/to/file_one.txt' or die $!;
    $filehash{$_}++ while <$fh>;
    close $fh or die $!;
}

{
    open my $fh, '<', '/path/to/file_two.txt' or die $!;
    while (<$fh>) {
        print qq("$_" is not in file one\n)
            if not exists $filehash{$_};
    }
}
[download]