This can happen when you protect your private keys with a default policy of DENY. The init script provided in the openssh-server rpm checks to see if the private key files exist under /etc/ssh. If the script can't find them, it executes ssh-kegen to generate them. The keys are actually there, ssh-keygen fails and the startup script exits.
To fix this, remove the check for the key files in the startup script:
start)
# Create keys if necessary
#do_rsa_keygen; <------------ Comment out these lines
#do_dsa_keygen;
echo -n "Starting sshd: "
if [ ! -f $PID_FILE ] ; then
sshd
RETVAL=$?
if [ "$RETVAL" = "0" ] ; then
success "sshd startup"
touch /var/lock/subsys/sshd
else
failure "sshd startup"
fi
fi
echo
;; |