On my Fedora Core 6, mailx is a link to mail
$ ls -l /bin/mailx
lrwxrwxrwx 1 root root 4 Oct 31 2006 /bin/mailx -> mail
the former is provided by the package redhat-lsb, the latter is provided by mailx. So, if things are not changed between the two Fedora releases, you should start to check the following
$ ls -l /bin/mail*
$ rpm -q mailx
$ rpm -q redhat-lsb
and eventually verify the integrity of the packages.