I saw similar messages on Ubuntu 9.04 ( my first attempt ), then I downgraded to Ubuntu 8.04 and Xephyr was running fine since then. Apparently it was some changes in 9.04, and while there is a patch, for my purposes it was easier to re-install Linux. It might be unrelated, but that's my experience. Did you install any update overnight?