I had the same problem where it would sometimes just click and not do anything, but then if I waited a bit it would start okay (or if I just really went at it).
Turned out to be my ignition switch going bad, as per this thread:
http://www.subaru-svx.net/forum/showthread.php?t=27339