Meaning of the yum error "Package tuple (...) could not be found in rpmdb"

Sounds like corrupt data. Do: yum clean all followed by yum update and then try the installation again.

You could try rebuilding the rpmdb

rpmdb --rebuilddb

This fixed a similar problem for me.

To solve that problem I had to do both:

yum clean all 
rpm --rebuilddb