I can't help, but I can tell you that with 10.9 I have similar problems from time to time. I don't restart, though, just give up and try later--and then the connection takes place. Usually. When I was running 10.8 and my wife was running 10.6, I sometimes had problems connecting to her computer.
Again, no help, but misery likes company, I hear.