Last week I yum-upgraded two boxes to F8 and they both exhibited a similar problem with ssh. Namely that I was unable to ssh to them until I restarted the ssh daemon, even after having rebooted. Reporting it here as suggested on the wiki page.