1 – «Audiência do Presidente da República (a Fulano).»

Neste caso, subentende-se: «Audiência (que foi concedida pelo) Presidente da República (a Fulano).»

A frase é passiva com ausência de verbo. Se subentendermos o verbo conceder, a preposição a antes de fulano passa a ter justificação. Frequentemente, as frases passivas contêm a preposição de em vez da preposição por.

2 – «Audiência com o Presidente da República (de Fulano).»

Aqui, a frase subentendida é a seguinte: «Audiência de Fulano com o Presidente da República.»

Conclusão: as frases apresentadas correspondem a diferentes formas de transmitir as mesmas ideias.