I have spent a bit of time doing this recently but with MR2 and CDH4 which may not be appropriate to your use case. However assuming some similarities, I suspect your problem is that you also need to override compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) on AvroKeyComparator.
The advantage to Avro is that Hadoop does not need to deserialize to sort in the shuffle. This function in RawComparator allows Hadoop to quickly compare the bytes directly.
Whilst this seems a bit daunting my trick to doing this in MR2 is to leverage Avro's excellent support for projections - subsets of schemas. For example let's say you want to "group" by attribute A but then "sort" by attribute B. In this case I would use a composite key with schema {A, B} and the out of the box AvroKeyComparator as the sort comparator. Then I would implement my own grouping comparator which uses a schema of just {A} then uses the BinaryData function to compare:
I assume you can do something similar in MR1.
NEW: Monitor These Apps!
elasticsearch, apache solr, apache hbase, hadoop, redis, casssandra, amazon cloudwatch, mysql, memcached, apache kafka, apache zookeeper, apache storm, ubuntu, centOS, red hat, debian, puppet labs, java, senseiDB