Thanks for making such an accessible golf problem (at least it feels so to me). here's 116 (my first golf):

sub f{my%h=@_;for(values %h){for(@$_){$h{$_}=[]if!$h{$_}}}
print join(', ',sort{(grep /^$b$/,@{$h{$a}})?1:-1}keys%h)}
[download]

update: cool, i can rip some stuff out if i assume the test harness that tadman provided. 97:

sub f{%h=@_;for(values %h){for(@$_){$h{$_}=[]if!$h{$_}}}
sort{(grep /^$b$/,@{$h{$a}})?1:-1}keys%h}
[download]