Those two sentences are indeed correct and equivalent, but in many situations that substitution is not possible. I was trying to come up with a little guide for you, but quickly got bogged down in detail. So I’m just going to give you some examples where the substitution works and some where it doesn’t.
Examples where it works
My impression is it generally works in your type of sentences, that is when you have a noun clause acting as subject of the verb in the main clause (termos/que tenhamos mais paciência is the subject of é):
É estranho eles não terem ainda chegado
É estranho que eles não tenham ainda chegado
Convém chegarmos lá cedo
Convém que cheguemos lá cedo.
Also when the noun clause is the predicative of the subject in the main clause (which is similar to your example and my first one: the noun clause and the main clause just swap roles):
O meu receio é eles já lá não estarem.
O meu receio é que eles já lá não estejam
It works with many noun clauses completing the meaning of other nouns and adjectives, but both sounds strange when the subject is the same in both clauses; then it is the impersonal infinitive that sounds good:
Tenho esperança de eles ganharem a corrida.
Tenho esperança (de) que eles ganhem a corrida
A mãe está desejosa de os filhos chegarem
A mãe está desejosa (de) que os filhos cheguem
[Fine:] Estamos desejosos de chegar
[Sounds strange:] Estamos desejosos de chegarmos
[Sounds strange:] Estamos desejosos (de) que cheguemos
It also works in adverbial clauses introduced by para and até:
Isto é para te lembrares de mim
Isto é para que te lembres de mim
Comecemos cedo para estar tudo pronto a horas
Comecemos cedo para que esteja tudo pronto a horas
Ainda vai demorar até estar tudo pronto
Ainda vai demorar até que esteja tudo pronto
Examples where it does not work
Quero que (tu) venhas cá.
[Wrong:] *Quero (tu) vires cá
Ele pediu que tu lá vás
[Wrong:] *Ele pediu tu lá ires
[But, with a different sintax:] Ele pediu para tu la ires
Embora sejamos pobres, ajudamos no que pudermos
[Wrong:] *Embora sermos pobres, ajudamos no que pudermos
It doesn’t work with adjective clauses:
Gosto de flores que† cheirem bem
[Wrong:] *Gosto de flores (que†) cheirarem bem
I doesn’t work with the independent subjunctive either:
Talvez eles estejam em casa
[Wrong:] *Talvez eles estarem em casa
Raios partam os cuscos
[Wrong:] *Raios partirem os cuscos
Note: † In all other examples, que is the conjunction that introduces the finite subordinate clause, but disappears in the infinitive clause. Here que is the relative pronoun; the infinitive clause is wrong with or without it.