Greetings,
another important Hidden Service issue, is the guard enumeration attack that was described by the "Trawling for Tor Hidden Services: Detection, Measurement, Deanonymization" paper (in section VII) [0].
A trac ticket was created to fix this issue (#9001 [1]). The most popular solution so far seems to be the 'Virtual Circuit' concept. The idea here is that if you have already created a circuit to a Rendezvous Point, and then that circuit fails and you need to connect to a different RP, then maybe you could reuse the previous hops of the circuit and only change the last hop to the new RP.
This is an interesting concept and useful in other occasions too. For example, if the network is flooded with CREATE cells (like during the recent botnet invasion) and relays reject them because of increased workload, then maybe clients shouldn't build entirely new circuits to send CREATE cells to different relays (because building new circuits increases the total load of the network even more).
However, this concept must be designed carefully and in a security-conscious way. Reusing parts of old circuits to connect to new nodes might result in unexpected attacks.
More solutions have been proposed in #9001, like "guard node layers", which need further investigations.
If you think you can contribute to this topic, please write your ideas in this mailing list or in ticket #9001.
Enjoy.
[0]: www.ieee-security.org/TC/SP2013/papers/4977a080.pdf [1]: https://trac.torproject.org/projects/tor/ticket/9001