I was receiving the following error when performing a yum update on a RHEL5 server running a XEN kernel with virtual machines installed:

Error: Missing Dependency: xen-libs = 3.0.3-64.el5 is needed by package xen

The problem is that the server was not subscribed to the virtualization channel on the RHNS server.
The entitlements section on RHN can be misleading here. It will say something similar to "Management, Virtualization" but this does not mean it is subscribed to the proper channels, only that the server is entitled to use those channels if you so choose.

Once the server was subscribed to the virtualization channel, yum update completed successfully.