Here is an explanation which might provide some intuition about what is going on here. Suppose that in your graph you have three vertices where vertex 1 is adjacent to both vertices 2 and 3, but vertices 2 and 3 are not adjacent to each other. Let $X_1$, $X_2$, and $X_3$ be the corresponding random variables being modeled. In this case you are wanting to have
\begin{align*}
\text{Corr}(X_1,X_2) &= \rho \\
\text{Corr}(X_1,X_3) &= \rho \\
\text{Corr}(X_2,X_3) &= 0
\end{align*}
There is some tension here, in the sense that these requirements become incompatible with each other as $|\rho|$ grows too large. Namely, if $X_1$ is strongly correlated with both $X_2$ and $X_3$, then at a certain point it is no longer possible for $X_2$ and $X_3$ to be uncorrelated with each other. In other words, there is some degree of transitivity that holds with correlations. This is quantified in general here, and in particular it can be shown that for $|\rho|>1/\sqrt 2$, the above conditions are incompatible. And as the other answer shows, in practice you will run into trouble even sooner, namely at the point $|\rho| \geq 1/2$, even for carefully chosen families of graphs.
An alternative approach would be to relax the constraint that the non-adjacent variables have exactly correlation 0. A natural way to do this is to change our focus away from directly modeling the covariance matrix $\Sigma$, to instead modeling the precision matrix $\Lambda = \Sigma^{-1}$. Namely, we model $\Lambda$ in basically the same way that we were modeling $\Sigma$ before:
$$\Lambda = I - \rho A$$
where $A$ is the adjacency matrix of the graph. Here $\rho$ no longer represents the correlation between neighboring variables; instead it represents their partial correlation, after controlling for all the remaining variables. To ensure that $\Lambda$ is positive definite (which is equivalent to $\Sigma$ being positive definite), we need to impose the restriction $|\rho| < 1/r$, where $r$ is the valency of the (regular) graph. Although this restriction may appear superficially similar to the crude sufficient condition $|\rho| < 1/r$ that arises when modeling $\Sigma$ directly, the situation here is completely different. This time, as $\rho \to 1/r$ the random variables approach correlation 1 with one another (in each connected component of the graph), and we could not ask for more than that.
An example might help illustrate how this works. Consider the cycle graph on 10 vertices. Because of the symmetry of the graph, the value of the $(i,j)$ entry of $\Sigma$ only depends on the distance between vertices $i$ and $j$, so we can concisely summarize the resulting correlations for various choices of $\rho$:
\begin{array}{lllllll}
\text{Distance}& 0& 1& 2& 3& 4& 5& \\
\rho = 0& \text{1}& \text{0}& \text{0}& \text{0}& \text{0}& \text{0}& \\
\rho = 0.1& \text{1}& \text{0.101}& \text{0.01021}& \text{0.001031}& \text{0.0001052}& \text{2.104e-05}& \\
\rho = 0.4& \text{1}& \text{0.5015}& \text{0.2537}& \text{0.1327}& \text{0.07805}& \text{0.06244}& \\
\rho = 0.49& \text{1}& \text{0.865}& \text{0.7654}& \text{0.697}& \text{0.657}& \text{0.6439}& \\
\rho = 0.499& \text{1}& \text{0.9826}& \text{0.9691}& \text{0.9596}& \text{0.9538}& \text{0.9519}& \\
\rho = 0.4999& \text{1}& \text{0.9982}& \text{0.9968}& \text{0.9958}& \text{0.9952}& \text{0.995}& \\\end{array}
Here the correlations shown in the table are defined by $\Sigma_{ij}/\sqrt{\Sigma_{ii}\Sigma_{jj}}$ where $\Sigma$ is given by $$\Sigma = \Lambda^{-1} = (I - \rho A)^{-1}$$
Again, the idea here is that even though non-neighboring variables are now correlated with each other, this correlation is only due to the mutual influence of neighbors connecting them. In the case of a multivariate Gaussian distribution this can be made more precise, as then each variable satisfies the Markov property that, given its direct neighbors, it is conditionally independent of all the non-neighboring variables (e.g., see here).