Avec « avoir l’air » il est possible d’écrire
Elle a     l’air tolérant : c’est son air, son allure générale qui   est qualifiée –> elle a l’air tolérant des personnes qui ont traversé beaucoup d’épreuves
et
Elle     a l’air      tolérante : l’expression verbale avoir l’air signifie ici sembler —> elle a l’air/elle semble tolérante
—
Mais
Avec : elle est de caractère tolérant, on n’a aucune expression verbale dans lequel il y aurait un nom susceptible de recevoir un adjectif. 
Elle est de caractère tolérant = elle a un caractère tolérant
Elle est de contact chaleureux = elle a un contact chaleureux
Il est de compagnie charmante = sa compagnie est charmante

Dans votre exemple, l’accord se fait bien avec le nom qui précède :
– Elle est de caractère tolérant (d’un caractère tolérant serait mieux), ils sont de caractère tolérant.
Votre doute vient peut-être de l’emploi éventuel de tolérant comme attribut du sujet :
– Elle est tolérante de nature, de tempérament.