This was extremely frustrating while trying to figure it out. Now that I have it is pretty obvious. I was configuring a FAST Search Server 2010 for SharePoint. In the Configuration Wizard at the Server settings screen, it asks for a Server name. The documentation says that this is the FQDN of the server. All my servers have their own name but also have an alias pointing to them. Of course, I always refer to these servers via their alias. So when it asked me for the server name, I naturally entered the alias. The wizard rejects this with a dialog box "Host name validation failed - Please provide a valid server name". I checked firewall settings, event logs and found nothing. It finally dawned on me to actually use the FQDN (easiest way to confirm this is to right click My Computer and select Properties) and it worked.
The strange thing is that if the wizard is able to determine an incorrect FQDN, then why couldn't it just set that value?