After further searching, I found my answer here:

http://groups.google.com/group/microsoft.public.sqlserver.olap/browse_thread/thread/41f4415a571315f1/ee39099c22277493?lnk=st&q=%22sqlbrowser+service+was+unable+to+establish+analysis+services+discovery%22&rnum=1#ee39099c22277493

Check that the service account has write permission on these directories:

C:\Program Files (x86)\Microsoft SQL Server\90\Shared

C:\Program Files (x86)\Microsoft SQL Server\90\Shared\ASConfig

That's what did it for...

I have this same problem, and this post is the only bit of information I have found about it so far.

I'm using SQL 2005 Evaluation Edition x64, with SP1, installed...