I can't reproduce that, at least on Perl 5.10.0.

#!perl -w
use strict;
use Data::Dumper;

my @Objs = map { +{num => int rand(500)} } 1..1000;

sub is_sorted {
    my $last;
    for (@_) {
        if (defined $last and $last->{num} > $_->{num}) {
            #print Dumper $last;
            #print Dumper $_;
            return 0
        };
        $last = $_;
    };
    return 1    
};

print "Unsorted\t",is_sorted(@Objs),"\n";
print "Sorted\t\t",is_sorted(sort { $a->{num} <=> $b->{num} } @Objs),"
+\n";

@Objs = sort { $a->{num} <=> $b->{num} } @Objs;
print "Sorted in-place\t",is_sorted(@Objs),"\n";
[download]

Most likely, your data is not what you believe it is. So, please reduce your code and data to a short, self-contained example that still exhibits the behaviour.

Update: Changed cmp to <=>, as that's what the code should use to mirror the OP.