It looks like you are using OpenAFS packages built for a specific kernel
- in this case the 5.5 kernel-2.6.18-194.26.1.el5. My guess would be
that in updating to 5.6, yum has automatically removed that older kernel.

You need to get kmod-openafs packages that match the version of your
currently running kernel. Where did you get these packages as they are
not a part of CentOS?

Thank you, Ned.

Here is what I ended up doing..

Thanks to Hyper V i could easily rollback to 5.5.

Downloaded kernel-2.6.18-194.26.1.el5.i686.rpm, manually installed it and after that yum update worked without any issues.

Thank you for pointing me into the right direction.

Asya