my @newarray = map { $_->[0] }
               sort { $a->[1] <=> $b->[1] }
               map { $_ => n_primes_less_than_25th_power($_) }
             @oldarray;

The essence is that each element of @oldarray is passed to the map which does the complex calculation on that element and creates a 2-element array containing the original element and the calculated value. Those are passed to the sort ...

There's a big problem here. The first map expression must return a reference to a two-element array to pass to sort:
    map { [ $_ => n_primes_less_than_25th_power($_) ] }

Note that the the  => (fat comma) in the above expression is just an idiosyncratic variation on the more common  , (comma) operator, so another version of the expression might be:
    map [ $_, n_primes_less_than_25th_power($_) ],
(which also dispenses with the enclosing  { ... } code block (update: because  [ ... ] is a simple expression); note this needs a terminating comma operator).

One way to easily control sort order is to realize that the  <=> and  cmp operators (see perlop) return (-1, 0, 1) as the result of their comparisons. If you have a scalar  $order that may have only the values 1 (ascending) or -1 (descending), it's easy to control ordering:
    sort { $order * ($a->[1] <=> $b->[1]) }
(among other ways, of course).

For tutorials on sorting and transformation sorts, see List Processing, Filtering, and Sorting, and in particular Understanding transformation sorts (ST, GRT), the details. See also A Fresh Look at Efficient Perl Sorting for an in-depth discussion of ST and GRT sorting.