Finalmente consegui corrigir esse problema. Não foi difícil como eu pensava! O cara no fedora estava certo.
costeletas, respondendo à pergunta (primeiro link da minha pergunta):
From what you've written, you installed both packages from a third-party repo instead of using the ones from the standard Fedora repo. If so, remove them, remove the repo they came from and then install the Fedora versions as that will bring in all of the needed dependencies. Once you have that done, we can worry about php.
Então eu executei esses comandos um após o outro:
yum remove php
%código%
%código%
yum remove php-common
Isso me fez voltar para onde eu comecei. Então eu segui este tutorial para reinstalar tudo: Tutorial