When I type “yum update” under RHEL 5.x server I get the following error:

Error: Missing Dependency: xen-libs
needed by package xen-3.0.3-105.el5_5.4.i386 (installed)

How do I fix this problem?

This dependency error error related to RHEL virtualization package. All you have to do is register your server the Virtualization channel in Red Hat Network (RHN). Login to your RHN account > Systems tab > Select your server > Alter Channel Subscriptions > Add the child channel Red Hat Enterprise Linux Virtualization > Save. Finally run the yum command again:
# yum update