There are several things that need fixing here:

• my $AoH_new = map ...
  [download]

  map generally returns a list, not an array ref. Here, you're calling it in scalar context, so it actually returns the number of items in its return list. This isn't what you want, judging by your variable names.

• my $AoH_new = map { $AoH_orig->[$_]{'title'} =~ s/ /_/g } @$AoH_orig;
  [download]

  For each item in the list, map executes the block with that item aliased to $_. But here you are treating $_ as an array index for @$AoH_orig, not as an element of $AoH_orig. Either map over the actual indices (0 .. $#$AoH_orig), or use something closer to your second example, which is:

• my $AoH_new = map { $_->{'title'} =~ s/ /_/g } @$AoH_orig;
  [download]

  Each time map executes the block, it accumulates the return value of the block in a list, and finally returns the list. In this case, you're accumulating the return values of "$str =~ s///g" statements. But these statements only return the number of changes made to the string. Again, it seems like you want modified copies of the strings in $AoH_orig, with a similar structure -- not a list of the number of changes made to each string.
• Since $_ is aliased to the elements of @$AoH_orig, the s/// inside the map actually modifies things inside of $AoH_orig. Again, probably not what you want.
• Even fixing all that, if you want to replicate the structure of $AoH_orig, you need to have a level of hashes in there somewhere. If you want an AoH, then each item in the array needs to be a hashref -- the map statement must return a list of hashrefs. So the map's block must evaluate to a hashref each time.

Here is maybe what you wanted to say:

my @AoH_new = map {       ## store the result in an array
    my %h = %$_;          ## make a copy of each hashref
    $h{title} =~ s/ /_/g; ## modify a value in the hash copy
    \%h;                  ## return a ref to that copy
} @$AoH_orig;
[download]

Or even better, perhaps:

use Storable 'dclone';
my $AoH_new = dclone $AoH_old; ## copy the old structure

## change an item in each hash in the new copy
$_->{title} =~ s/ /_/g for @$AoH_new;
[download]

Update: changed "$h->" to "$h" in my example. Thanks Errto.