Eu seguiria diretrizes Debian para atualização : isso significa atualizar seu sistema básico primeiro, depois o resto; se eu fosse você, eu deixaria o Debian escolher qual atualização de pacote primeiro.
Caso você queira atualizar manualmente cada um dos seus pacotes "relevantes", eu seguiria esta ordem: mysql, java, tomcat.
Lembre-se que você provavelmente mudará de sun-jdk6 para openjdk7, se bem me lembro.
Para obter uma versão empacotada do jdk do oracle, dê uma olhada no java-package