"Rejeição: CT-e a ser substituído deve estar com a situação autorizada".

Essa rejeição ocorre porque o CTe que você está tentando substituir não está autorizado. Ou seja, para emitir um CTe de Substituição, o CTe original precisa estar autorizado (não pode estar cancelado ou denegado).