Olá André.
Acho que o caminho entre a foto digital e o resultado final de impressão, está se tornando um verdadeiro calvário...dependendo do lugar em que estamos e da disponibilidade de laboratórios!!
Pelo que mostrou aparenta que ocorreu uma perda significativa de resolução da foto, como se tivesse enviado um arquivo com tamanho reduzido e ocorrido uma ampliação.
Como entregou os arquivos? Qual a resolução? Aplicou sharpening na exportação para compensar a perda da nitidez com o resize?
Moro em Belo Horizonte, e atualmente imprimo meus trabalhos (pessoais e amadores) em uma loja de confiança, no Centro da Cidade - Pedro Cine Foto, o custo é menor do que revelar em quiosques dentro do shopping, mas maior que em grandes lojas de departamento...
É importante lembrar que o tratamento deve ser direcionado para a impressão, no meu caso elevo um pouco os pretos, e aumento o contraste, mantendo o arquivo final dentro do gamut de impressão, ao exportar seleciono sharpening médio para papel e faço o resize baseado em um preset com as dimensões exatas do arquivo em cm. Envio ao Lab com a informação de não aplicar nenhum ajuste adicional e assim é feito.
Abraços e boas fotos