A versão 7 do openjdk só estava disponível nos repositórios padrão do Ubuntu para o Oneiric (11.10).
Tanto o maverick (10.10) quanto o natty (11.04), somente a versão 6 do openjdk está disponível.
Você tem algumas opções.
Primeiro, considere a atualização de 11.04 a 11.10. Você provavelmente já está considerando isso desde que você está ciente de que Maverick está prestes a perder seu apoio oficial.
Alternativamente, você pode querer considerar a instalação do Oracle Java - v6 ou v7