I did it with an Hoh. Not sure if it's the best way... just what my instinct popped out...

use strict;
use warnings;
my $users = {};
$users->{fred}->{count}=1;
$users->{sarah}->{count}=2;
$users->{arthur}->{count}=1;
$users->{benjamin}->{count}=10;
$users->{phil}->{count}=3;
$users->{betty}->{count}=4;
$users->{ilsa}->{count}=5;

print $_ . "\n" for sort { $users->{$a}->{count} <=> $users->{$b}->{co
+unt} } keys %$users;
[download]

UPDATE: Or, you could use a hash, like the op did:

use strict;
use warnings;
my %users;
$users{fred}->{count}=1;
$users{sarah}->{count}=2;
$users{arthur}->{count}=1;
$users{benjamin}->{count}=10;
$users{phil}->{count}=3;
$users{betty}->{count}=4;
$users{ilsa}->{count}=5;

print $_ . "\n" for sort { $users{$a}->{count} <=> $users{$b}->{count}
+ } keys %users;
[download]

For me the HoH seems more "readable" but I couldn't say why. timtowtdi...