Should I just format the original server and start over with "The Perfect Server Instructions" for both?
Something is seriously wrong with your setup and there is no point in stressing about it. Just start over if at all possible.
If I were you I would try Debian this time. I really like Ferdora also but mainly on a desktop PC. There is much more help for Debian in my experience. You can go with either Ubuntu server or Debian Sqeeze.
Follow this howto if you go with Debian Sqeeze:
It is a fairly robust setup - remember to follow it to the letter.
Download the PDF version and then use putty to copy and paste the commands but also remember to replace hostnames and server information with your own.
Good luck with it.
If you get stuck at any step someone will help you on this forum.
What is your hardware setup (general setup only - not the exact details)