Olá Bruno,
Esta dúvida é bastante recorrente. Eu ainda a possuo, mas, confesso, já aceitei a ideia de que o aviso prévio (trabalhado ou indenizado) também conta como tempo de serviço para a contagem do aviso prévio por tempo de serviço.
Em que pese grande discussão a respeito do assunto, devemos ter por base que trata-se de "direito dos trabalhadores", ou seja, qualquer redução deve ser a estrito senso. Se você não considerar o período do aviso prévio na contagem do tempo de serviço, você estará reduzindo um direito. Outro ponto que deve ser analisado é o famoso "o aviso prévio, mesmo que indenizado, conta como tempo de serviço para todos os efeitos". Por último, temos o caso das férias, que traz uma semelhança como caso questionado, pois, o período de gozo de férias conta como tempo de serviço para se ter direito à novo período de férias.
Assim, pelas ideias acima tecidas, embora haja muita discussão acerca do assunto, entendo que no seu caso concreto, o aviso prévio é de 39 dias.
Aqui no TRT/PR são editadas revistas eletrônicas com assuntos diversos. Em Julho/2013 teve esta matéria em foco e você vai notar que, mesmo na revista, os autores divergem entre si. (Tente acessar pelo site http://www.mflip.com.br/temp_site/edicao-2212.pdf, ou acesse o site do TRT do PR e pesquise lá).
Por fim, como você terá que homologar a sua rescisão de contrato, oriento que entre em contato com o Sindicato Profissional e consulte a posição deles, que, muito provavelmente, deverá corroborar com a minha e os demais colegas que possuem o mesmo entendimento.
Espero que tenha ajudado.