I haven't carried out this installation myself, but I might be able to help.
sendmail service is running, but I can't telnet to 25
With regards to being able to telnet to port 25, have you checked what iptables is doing? I use FC3 on my desktop at work at the moment, and if I remember correctly, depending on what you selected during install, you can end up with a fairly restrictive policy on your machine.
It's essentially a firewall, and you can view what you have set up with
cyrus-imapd service won't even start.
What error messages are you getting when trying to start this up? If it's not logging it to the console, it should be in the messages file, or syslog. If you could post that here, it could be helpful in solving your problems.