I am hi-jacking this thread. I have a similar problem as srivasuk described: I have a Windows global admin account under which all SQL Processen run. I receive the same cannot-login-failure, made this account explicitly member of the Windows Administrators group. Did not work, gave it explicitly SA role within SQL Server, still I receive this cannot-login-error.
Now, I can try one of the solutions given, but I would like to understand what is happening here. Also, it is policy here to use this specific global account for these services. In another, similar, SSAS setup this account gives no problem. Obviously there must be a difference, but I cannot find what that is.
Any other hints?
EDIT/SOLUTION: I found out that the datasources of the cubes where pointing to an alias, which is used on all servers of a specific OTAP que. This new server did not yet have this alias installed, hence the login failure. I am amazed however why I get this cannot-login-error, and not a cannot-find-server/alias...