I'm having a similar issue, SSAS 2005. I can ping the machine by name, IP, and FQDN. I can RDP to the machine. I've tried swapping out service accounts, and of course restarting SSAS multiple times. Using the SQL Server 2005 Surface Area configurator tool, I see that neither "local connections" nor "local and remote connections" is chosen, and when I try to select one of those radio buttons, a message says that a restart of that service will be needed, followed by another pop-up that says (again) this instance (of SSAS) cannot be found on localhost.