So if I make small changes to allow the code to be run in a test harness I get:

use strict;
use warnings;

my $HostA = bless {name => 'data_123'};

my ($fsObj) = $HostA->find(
    type       => 'DS',
    criteria   => {name => qr/^data_123$/i},
    force_sync => 1,
    );

print $fsObj || 'not matched';

sub find {
    my ($self, %params) = @_;

    foreach my $k (keys %{$params{criteria}}) {
        my $objVal = $self->getProperty($k);

        my $critVal = $params{criteria}{$k};
        if (defined $objVal) {
            return 0 if (!($self->_compareCriteria($objVal, $critVal))
+);
        }
    }
    
    return 'All matched';
}

sub _compareCriteria {
    my ($self) = shift(@_);
    my ($objectVal, $critVal) = (@_);
    if (ref($critVal) eq 'Regexp') {
        return ($objectVal =~ $critVal) ? 1 : 0;
    }
}


sub getProperty {
    my ($self, $prop) = @_;
    
    return $self->{$prop};
}
[download]

which prints:

All matched
[download]

Maybe you'd like to modify that to show the problem you see?

Update: as an aside, this doesn't look like new code written by someone with an apparently limited understanding of regular expressions. Is this maintenance work by someone thrown in at the deep end perhaps?