Eu quero escrever uma classe par genérica, que tem dois membros: chave e valor. O único requisito para essa classe é que tanto a chave quanto o valor implementem a interface Comparable, caso contrário, a classe Pair não os aceitará como parâmetro de tipo.
Primeiro eu codifico assim:

public class Pair<T1 extends Comparable, T2 extends Comparable>

Mas o compilador JDK 1.6 irá gerar um aviso sobre isso:

Comparable is a raw type. References to generic type Comparable<T> should be parameterized

Então eu tentei adicionar parâmetros de tipo e o código agora se parece com isso:

public class Pair<T1 extends Comparable<? extends Object>,
                  T2 extends Comparable<? extends Object>>

Agora tudo corre bem até que eu tentei gerar um Comparator for Pair. (O código a seguir está na classe Pair)

public final Comparator<Pair<T1, T2>> KEY_COMPARATOR = new Comparator<Pair<T1, T2>>() {
        public int compare(Pair<T1, T2> first, Pair<T1, T2> second) {
            *first.getKey().compareTo(second.getKey());*
            return 0;
        }
    };

O códigofirst.getKey().compareTo(second.getKey()); irá gerar um erro dizendo:

The method compareTo(capture#1-of ? extends Object) in the type Comparable<capture#1-of ? extends Object> is not applicable for the  arguments (T1)

Alguém sabe o que esta mensagem de erro significa?
Quaisquer sugestões sobre este tópico são bem vindas.

ATUALIZAR:
Aqui está o código completo:

public class Pair<T1 extends Comparable<? extends Object>, T2 extends Comparable<? extends Object>> {
    private T1 key;
    private T2 value;

    public static int ascending = 1;
    public final Comparator<Pair<T1, T2>> KEY_COMPARATOR = new Comparator<Pair<T1, T2>>() {
        public int compare(Pair<T1, T2> first, Pair<T1, T2> second) {
            int cmp = first.getKey().compareTo((T1)(second.getKey()));
            if (cmp > 0)  return ascending;
            return -ascending;
        }
    };
}

@MarvinLabs Você pode explicar um pouco mais por que o compilador não pode garantir que os objetos sejam comparados a outros objetos do mesmo tipo. No código acima,second.getKey() retorna o tipo T1, que é do mesmo tipo quefirst.getKey()