Vc não quer formatar uma hora (um tempo) vc quer formatar um intervalo de tempo. Como seu objectivo é formatar um intervalo vc pode criar o seu proprio Formater pois a formação resume-se a dividir por 60 cada uma das partes. Se vc suar Date ou Calendar eles vão intrepretar os milisegundos como decorrentes a apartir do inicio da epoca do java e vc terá que despresar os anos. Supondo que no seu caso isso não é um problema então a solução é fazer: