Segundo Celso Pedro Luft, no Dicionário Prático de Regência Verbal, o verbo trocar, no sentido de «permutar», tem, além de um sujeito (quem troca), um complemento/objecto directo (coisa ou pessoa trocada) e um complemento preposicional (coisa ou pessoa pela qual se faz a troca). A preposição deste complemento é por, mas os exemplos dados por Luft sugerem que com é também possível se o complemento preposicional for preenchido com um nome com om traço [-humano].
Outras regências e significações são possíveis:
a) trocar por, «preferir» («trocar um clube por outro»);
b) trocar com, «confundir» («Trocar uma pessoa com outra») e «dar e receber reciprocamente» («Trocar olhares com alguém»);
c) trocar-se em, «transformar-se» («Trocar(-se) o dia em noite»);
d) trocar de (ou só trocar), «mudar» («trocar de roupa/trocar a roupa»);

Como verbo transitivo directo, «B>tocar significa ainda «tomar em vez de outro» («Ela trocou a sombrinha»), «alterar, modificar» («Trocar os lugares») e «cruzar (as pernas)» («pernas trocadas»).

O caso da frase apresentada pela pergunta tem mais que ver com a aceitabilidade da preposição com associada a entidades descritas como seres humanos. O uso desta preposição, que parece seleccionar nomes relativos a coisas, de acordo com Luft (ver mais acima), sugere que tais entidade são identificadas com objectos. Afigura-se, portanto, mais adequado o uso da preposição por, que não sugere tal leitura. A frase correcta é, portanto: «Na programação proponho trocar o Pedro Abrunhosa pelo João Pedro Pais.»
Todavia, o uso de com pode ter cabimento se estivermos perante o caso em que «Pedro Abrunhosa» e «João Pedro Pais» são expressões elípticas para «o disco do Pedro Abrunhosa/ João Pedro Pais». Se assim for, omitiu-se «o disco», mas os nomes próprios estão em seu lugar, mantendo a propriedade [-humano], mais compatível com com.