Hello,
Ryan is right. The mirrors need to sync up. That's most likely the cause. Still, it's curious why you have two kernels listed in grub.conf and only one listed from yum. You should also see the 2.6.18-238.el5xen kernel listed.
Well, I copied the /var/cache/yum/timedhosts.txt file from server 1 to server 2. Then run yum update and all kinds of errors came flying at me. So I just SCP'ed the whole /var/cache/yum directory of server 1 to server 2. Ran yum update and there were the updates I was missing including the new kernel-xen. I don't know if this was the *proper* way of fixing it but it did the job :P.