First notice that there is a typo in your algebra,
$$ \operatorname{Var}(aX+bY) = a\operatorname{Var}(X)+b\operatorname{Var}(Y)\boldsymbol{\color{red}{+}}2ab\operatorname{Cov}(X,Y).$$
It might be helpful to then set this up as a constrained maximization problem, i.e.
$$ \min_a (a^2\sigma_{X}^2+(1-a)^2\sigma_{Y}^2+2a(1-a)\rho\sigma_{X}\sigma_{Y}) $$
subject to
$$ a \ge 0 \quad \text{and} \quad a \le 1. $$
Notice that the second derivative of the objective function is positive,
$$ 2(\sigma_{X}^2+\sigma_{Y}^2-2\rho\sigma_{X}\sigma_{Y})=2\operatorname{Var}(X-Y)>0 ,$$
and since it is quadratic in $a$ it is a convex parabola and its minimum is going to be either the critical point of the parabola or the boundary. Accordingly, setting the first derivative of the objective function with respect to $a$ to zero leads to
$$(2\sigma_{X}^2-4\rho\sigma_{X}\sigma_{Y}+2\sigma_{Y}^2)a+(2\rho\sigma_{X}\sigma_{Y}-2\sigma_{Y}^2) = 0 $$ and therefore the critical point of the parabola is given by
$$ a^{c} = \frac{\sigma_{Y}^2-\rho\sigma_{X}\sigma_{Y}}{\sigma_{X}^2-2\rho\sigma_{X}\sigma_{Y}+\sigma_{Y}^2}. $$
and the solution is
$$ a^* = \begin{cases}
0\;\quad\text{, if}\quad a^c \le 0\\
1\;\quad\text{, if}\quad a^c \ge 1\\
a^{c}\quad\text{, otherwise.}
\end{cases} $$
Finally, notice that
$$ a^c \le 0 \iff \sigma_{Y}\ge\rho\sigma_{X},$$
and
$$ a^c \ge 1 \iff \rho\sigma_{Y}\ge \sigma_{X}.$$
Somewhere you stopped applying $\frac{1}{n^2}$ to the right-hand side of your expressions
You should have ended up with $$\text{Var}(\bar{X}) =\frac{1}{n^2}\left(n\text{Var}(X)+2 \frac{n(n-1)}{2} \rho\text{Var}(X)\right) =\frac{1+(n-1)\rho}{n} \text{Var}({X})$$
which, as expected, is $\frac{1}{n} \text{Var}({X})$ when $\rho=0$, and is $ \text{Var}({X})$ when $\rho=1$
Best Answer
$\newcommand{Cov}{\operatorname{Cov}}$ $\newcommand{Var}{\operatorname{Var}}$ The formula states $$\Var\left(\sum_{i=1}^nX_i\right)=\sum_{i=1}^n\Var(X_i)+\sum_{i\neq j}\Cov(X_i,X_j).$$ If the double sum is confusing you, it might be worth writing it out in full for small values of $n$, e.g. \begin{align*} \Var(X_1+X_2)=\Var(X_1)&+\Var(X_2)+\Cov(X_1,X_2)+\Cov(X_2,X_1) \\ \Var(X_1+X_2+X_3)= \Var(X_1)&+\Var(X_2)+\Var(X_3)\\ &+\Cov(X_1,X_2)+\Cov(X_2,X_1) \\ &+\Cov(X_2,X_3)+\Cov(X_3,X_2) \\ &+\Cov(X_3,X_1)+\Cov(X_1,X_3). \end{align*} You'll note that the double sum is over all ordered pairs $(i,j)$ with $i\neq j$ as $i,j$ each vary between $1$ and $n$. So we want to know the number of such pairs (which is the number of lots of $\rho$ that we are summing).
There are $n$ choices for $i$ (namely $1,2,\dots,n$). Given an $i$, there are then a further $n-1$ choices for $j$ s.t. $i\neq j$. So we have $n(n-1)$ terms in the double sum.
Putting everything together, you get a final answer of $\boxed{n+n(n-1)\rho}$.