Prgmr.com uses the Xen hypervisor, our current servers all use Xen 3.3 or 3.4. (we have some older servers on 3.1 but we are slowly moving customers off those.)
NetBSD 5 is known to work on the current prgmr.com systems.
[FreeBSD] Xen support is in its infancy, but the stuff in 8-CURRENT only works on Xen hypervisor version 3.2 and above, so this should work with the newer prgmr.com servers running Xen 3.3, however, I don't know of anyone successfully working on it.
Centos 5.x, Debian 4.0, debian 5.0, Ubuntu 8.04, 8.10, 9.04, and Gentoo are known to run on prgmr.com systems. Ubuntu 8.10 and fc10 will work with distro kernels now that prgmr.com has Xen 3.3 servers up and running.
Anything that uses a kernel.org kernel newer than 2.6.27 or so should work fine with paravirt_ops.