Using Fedora core 10, elvis "makes" OK. It will even run in an xterm. But trying to run it under X11, it tells me that it can't load the default font and so it bombs. I've tried to use the -fn "font-name" option but it tells me it can't load the font I give it even though I'm asking for a font that is known to X. I fully admit that fonts in Linux are a complete mystery to me so I haven't been successful in installing the default font and I'm probably not specifying the font name properly in the option. Help anybody?

Ps it used to run in Fedora 6 without any problem.

Try with:

elvis -G x11

Elvis is dead.

No, he's just left the building.

I had a similar issue yesterday - trying to start from the menu, I got something like "*-courier-medium-r-*-18-* font not found" I created a .elvisrc file in my home directory, and changed the name of the default fonts to the 12 point versions (according to Xfontsel, I don't have the 18 point version of Courier). It didn't work.
But today, when I turned on my laptop (and did another aptitude update/safe-upgrade - which didn't change anything relevant, so far as I know) Elvis is working from the menu AND from console.
Sorry, I know this isn't very helpful, but I'm trying to solve the same problem as you.
Good luck.

BTW, I'm running Debian Squeeze, not Fedora 10.