Hi Jamie,
I think I pinned down the source of your problems. The problem is rooted in the fact that we require non-authenticated access to the XML RPC plugin on the trac server side during authentication.
If you have raised the debug level in your trac installation you probably find lines like the following:
12010-10-13 12:54:06,043 Trac[main] DEBUG: Dispatching <Request "POST '/xmlrpc'">
22010-10-13 12:54:06,046 Trac[cache] DEBUG: cache metadata undefined (youngest_rev=0)
32010-10-13 12:54:06,046 Trac[cache] INFO: repos rev [0] != cached rev [None]
42010-10-13 12:54:06,046 Trac[api] INFO: Synchronized '' repository in 0.00 seconds
52010-10-13 12:54:06,046 Trac[web_ui] DEBUG: RPC incoming request of content type 'text/xml' dispatched to <tracrpc.xml_rpc.XmlRpcProtocol object at 0xdb69dd0>
62010-10-13 12:54:06,046 Trac[web_ui] DEBUG: RPC(XML-RPC) call by 'anonymous'
72010-10-13 12:54:06,047 Trac[xml_rpc] DEBUG: RPC(xml) call by 'anonymous', method 'ticket.component.getAll' with args: ()
82010-10-13 12:54:06,047 Trac[session] DEBUG: Retrieving session for ID '3d009e75afdbaff2095d14f8'
92010-10-13 12:54:06,048 Trac[perm] DEBUG: No policy allowed anonymous performing XML_RPC on None
102010-10-13 12:54:06,048 Trac[web_ui] ERROR: RPC(XML-RPC) Error
11Traceback (most recent call last):
12 File "/opt/python/lib/python2.6/site-packages/TracXMLRPC-1.1.0_r9171-py2.6.egg/tracrpc/web_ui.py", line 149, in _rpc_process
13 req.perm.require('XML_RPC') # Need at least XML_RPC
14 File "build/bdist.linux-x86_64/egg/trac/perm.py", line 576, in require
15 raise PermissionError(action, resource, self.env)
16PermissionError
To circumvent this you must give the access rights to the XML-RPC plugin to non authenticated users as well as authenticated ones as shown below:

And yes this should have been part of the documentation ... so sorry for the hassle. If possible we will try to avoid requiring unauthenticated access (I don't like this) - I will keep you updated on further progress.
HTH - thanks for your support,
Regards, Torsten
P.S.: The Mylyn access was just to crosscheck the availability of the service.