I was just about to respond in the same way as jdporter, but I thought I'd run a benchmark first. To my surprise, the key sort is faster than the indexed GRT! Assuming my benchmark isn't screwed:

#! perl -slw
use strict;
use Date::Calc qw(Decode_Date_US);
use Data::Dumper;
use Benchmark qw[ cmpthese ];

sub convertdate {
    return sprintf '%04d%02d%02d', Decode_Date_US( $_[0] )
}

our @list = (
  { fname => 'Jan', lname => 'Krynicky', birth_date => 'Sep 3 1975', }
+,
  { fname => 'Pavel', lname => 'Krynicky', birth_date => 'Dec 25 1969'
+, },
  { fname => 'Martin', lname => 'Krynicky', birth_date => 'Aug 24 1973
+', },
  map{
      {
          fname => $_, lname => 'Krynicky',
          birth_date => 'Jan 1 ' . ( 1900 + int( rand 100 ) )
      }
  } 1 .. $ARGV[ 0 ] || 100
);

cmpthese -1, {
    ST => q[
        my @sorted = map{
            $_->[1]
        } sort{
           $a->[0] <=> $b->[0]
        } map{
            [ convertdate($_->{birth_date}), $_ ]
        } @list;
    ],
    KEY => q[
        {
            my @keys = map convertdate($_->{birth_date}), @list;
            @sorted = @list[ sort {$keys[$a] cmp $keys[$b]} (0..$#list
+) ];
        }
    ],
    GRTish => q[
        my @sorted = @list[
            map {
                substr( $_, 8 )
            } sort map {
                convertdate( $list[$_]->{birth_date} ) . $_
            } 0 .. $#list
        ];
    ],
};
[download]

the keyed sort works out between 20 and 35% faster for this application.

       s/iter     ST GRTish    KEY
ST       1.67     --    -4%   -24%
GRTish   1.61     4%     --   -21%
KEY      1.27    32%    27%     --

C:\test>junk9 1
          Rate GRTish     ST    KEY
GRTish 21914/s     --   -10%   -19%
ST     24349/s    11%     --   -10%
KEY    27113/s    24%    11%     --

C:\test>junk9 1e2
         Rate GRTish     ST    KEY
GRTish  986/s     --    -1%   -16%
ST      997/s     1%     --   -15%
KEY    1179/s    20%    18%     --

C:\test>junk9 1e3
         Rate     ST GRTish    KEY
ST     71.2/s     --   -11%   -25%
GRTish 80.3/s    13%     --   -16%
KEY    95.1/s    34%    19%     --

C:\test>junk9 1e4
         Rate     ST GRTish    KEY
ST     6.31/s     --    -9%   -23%
GRTish 6.90/s     9%     --   -16%
KEY    8.23/s    30%    19%     --
[download]