Vamos perguntar ao aptitude:
aptitude why-not openjdk-7-jdk openjdk-6-jdk
Unable to find a reason to remove openjdk-6-jdk.
(a primeira linha diz: aptitude porque não instalar o openjdk-6-jdk se eu tiver o openjdk-7-jdk instalado)
Então, a resposta curta é: sim.
Resposta longa: se você usar o apt-get para fazer isso, você pode. Se você tentar fazer o mesmo com o Java da Oracle, prepare-se para ter alguns problemas.