repoquery --tree-requires ... [...] seems to be broken here,
Ah, it's just Adobe's packages that are broken and confuse the
depsolving. For example:
$ repoquery --whatprovides libgcc_s.so.1
libgcc-0:4.5.1-4.fc14.i686
AdobeReader_nor-0:8.1.7-1.i486
AdobeReader_ita-0:8.1.7-1.i486
AdobeReader_suo-0:8.1.7-1.i486
AdobeReader_kor-0:8.1.7-1.i486
AdobeReader_sve-0:8.1.7-1.i486
AdobeReader_dan-0:8.1.7-1.i486
AdobeReader_nld-0:8.1.7-1.i486
AdobeReader_chs-0:8.1.7-1.i486
AdobeReader_esp-0:8.1.7-1.i486
AdobeReader_ptb-0:8.1.7-1.i486
AdobeReader_cht-0:8.1.7-1.i486