I normally am a sucker for anything involving time travel and paradoxes and I tend to prefer linear gameplay. Jon Ingold is also one of my favorite authors. So All Roads should be right up my alley. I judged the 2001 IF competition and remember giving this one a score of "6" and then being surprised it took first place and won a whole slew of XYZZY awards. I decided to play it again recently to see if time would change my mind, but I left once again feeling underwhelmed.
At first, I thought I was bothered that the shifts and paradoxes were so fast and furious that I didn't have time to get a grip on the characters or their motivations. But Shrapnel and Shade are both similar in this regard and it didn't bother me there.
But looking at Jim Kaplan's review, I think he nailed it: Ingold does not trust the player here. If you spend too much time experimenting in any particular area, the game practically force feeds you what you should type, getting you to the ending as fast as possible. I play interactive fiction because I find satisfaction in being involved in the story, even if minimally, and here I felt like a puppet on a string.
That said, it's short enough that everyone should give it a try to see if it's up their alley.