Removing a Host Header is not necessary - the FrontPage Server Extensions will work fine with Host Headers. I would be more concerned with how FPSE is set up and configured on the server and whether some configuration setting is preventing FPSE from working.
Here are a few additional things to check:
1. From your initial post I can see that you've already gone through the walkthrough for installing FPSE on your WS2008 computer, but did you use the web-based or command-line-based installation for FPSE on your Default Web Site? Either way should work, but using the web-based installation allows you to administer FPSE on your Default Web Site and I'm curious if that succeeds.
2. Can you browse to the following URL?
http://yourserver/_vti_inf.html
That file is used by a remote computer to discover FPSE capabilities on a server, so if you can't browse that file then there's an issue.
3. Can you browse to the following URL?
http://yourserver/_vti_bin/shtml.dll
You should see the following message displayed in your browser:
Cannot run the FrontPage Server Extensions on this page: ""
That error message actually means that FPSE is working correctly, but it's a great test for basic functionality.
4. Does your web site have a custom HTTP header for MS-Author-Via: MS-FP/4.0 configured? (This would be under HTTP Response Headers in IIS7's IIS Manager.)