It's weird because I have a nearly identical box and setup and I can update the ovzkernel-PAE* just fine but on this box it doesn't work.
I only get this error with the openvz.repo and not others such as Centos-Base.repo
With my other server it works normally:
================
Setting up Update Process
Resolving Dependencies
--> Running transaction check
---> Package ovzkernel-PAE.i686 0:2.6.18-238.12.1.el5.0........