Ambas as construções são aceitáveis, embora correspondam a realidades sintático-semânticas distintas.

O adjetivo trajado pode construir-se com um complemento introduzido pela preposição de. Este complemento está, muito frequentemente, relacionado com a indicação de cor:

(1) «Ele chegou trajado de vermelho.»

Nesta ótica, a construção apresentada pelo consulente é correta, sendo mais natural sem a utilização do determinante artigo indefinido um:

(2) «trajado de (um) fato avermelhado»

Não obstante, o adjetivo trajado também pode ser acompanhado por um constituinte que é seu modificador, o que significa que este poderá ser eliminado da frase, pois não é pedido pelo adjetivo:

(3) «Ele chegou trajado com fato a rigor.»

Nesta frase, o constituinte «com fato a rigor» modifica o adjetivo trajado contribuindo para restringir a sua significação. No entanto, pode ser omitido da frase:

(4) «Ele chegou trajado.»

O constituinte «com um fato avermelhado», na frase (5) poderá ser usado com uma função equivalente à que se descreveu:

(5) «trajado com fato avermelhado»

Neste expressão, a informação central é a de que alguém está vestido (= trajado), contribuindo o constituinte «com um fato avermelhado» para exprimir uma informação acessória.

Note-se, no entanto, que, em termos semânticos, a diferença entre as construções (1) e (5) é, na prática, mínima.

Disponha sempre!