I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.
For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed). For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.
I believe your conjecture is equivalent to:
If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.
So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements). This would take less than $n^4$ time.
I admit two possible flaws in my argument. First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!). I find this highly unlikely. Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.
Final thought. Have you tried this out for all, say, 3-regular graphs for size 8 or so? I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.
