Unfortunately, the paravirt opts bits that are used for Xen domU support are only functional with kernel-PAE on i686 (and not in the i586 kernel at all). So the finagling to switch images/xen for i686 will be coming back soon, but with kernel-PAE bits instead of kernel-xen (*sigh*)
Is this really a new special case? Or can it just be part of the generic "what kernel is right for this hardware?" choice that picks PAE/smp now? (There is something like that, right?) When the "hardware" is paravirtual, that's just a particular flavor of "hardware" for which there is a right kernel.