If you have the choice, it is easier to avoid storing the duplicates than it is to remove them later.

use strict;
use warnings;
use Data::Dumper;
my $HASH1 = {
    'California' => [ 'Barstow' ],
};

my $new_value = 'Barstow';
if (!grep {/$new_value/} map( @{$_}, values %$HASH1)){
   push @{$HASH1->{California}}, $new_value;
} 

$new_value = 'other';
if (!grep {/$new_value/} map( @{$_}, values %$HASH1)){
   push @{$HASH1->{California}}, $new_value;
} 

print Dumper($HASH1);
[download]

Note that map allows grep to search the entire hash, as required by your later question.