$$\newcommand\ee{\vec{e}}
\newcommand\vv{\vec{v}}
\newcommand\XX{\vec{X}}
$$
Let me start by clarifying your example.
Let $S$ be the unit circle embedded in the plane with the usual parameterization $\phi(\theta)$, and let $\XX$ be a vector field on $S$.
This means that each $\XX(\theta)$ is in the tangent space of $\phi(\theta)$, which is the one-dimensional space spanned by $(-\sin\theta, \cos\theta) = \vec{\phi'}(\theta)$.
Let's first motivate what we mean by covariant derivative. So far, $\XX$ is a nice map from $[0,2\pi)$ to the tangent lines of $S$.
In general, its ordinary derivative $\XX'$ is going to be in $\mathbb{R}^2$.
We can write $\XX(\theta) = f(\theta)\vec{\phi'}(\theta)$, where $f$ is a nice real-valued function. Then $\XX'(\theta) = f'(\theta)\vec{\phi'}(\theta)+f(\theta)\vec{\phi''}(\theta)$,
and we note that $\mathbb{R}^2$ is spanned by $\vec{\phi'}(\theta)$ and $\vec{\phi''}(\theta)$.
When we want to study $S$ intrinsically, this differentiation is not good enough, because it can give us information which lies outside the tangent lines.
So we instead take its projection. Let $\pi(\theta)$ be the projection onto the subspace spanned by $\vec{\phi'}(\theta)$,
and instead consider $\pi(\theta) \circ \XX'(\theta)$. We call this new function $\nabla_\theta \XX$; it tells us only about the part of the derivative of $X$ which lies along $S$.
We now turn to the problem of parallel transport. Suppose now that $\XX(0)$ is a tangent vector at $\phi(0)$.
We want to roll it along $S$ to get a tangent vector $\XX(\theta)$ at $\phi(\theta)$ that is in some sense equivalent.
Now clearly we can take $\XX(\theta) = |\XX(0)|\vec{\phi'}(\theta)$, but it is worth elaborating on the machinery behind this intuitive operation.
The key here is that our rolling is in some sense maximally intrinsic. At every step, the intrinsic part of the vector does not change.
To formalize this, we say that $\nabla_\theta \XX(\theta) = 0$.
This defines the parallel transport of $\XX(0)$.
What if instead of starting with an intrinsic derivative, we started with a notion of parallel transport? Can we recover an intrinsic derivative?
Suppose that $\psi(\theta)$ is the map that gives the parallel transport of tangent vectors at $\phi(0)$ to the tangent space at $\phi(\theta)$. This is in fact linear.
Let $\XX(\theta)$ be a vector field on $S$.
We want to recover the intrinsic component of the infinitecimal change of $\XX$ at $\theta=0$.
To do that, let $\delta>0$ be some small change in $\theta$. Can we recover the intrinsic change of $\XX(\delta)$ from $\XX(0)$?
Well, we know what $\XX(\delta)$ should look like if there is no intrinsic change at all: it is just the parallel transport $\psi(\delta)(\XX(0))$.
So we recover the intrinsic change of $\XX(\delta)$ as the difference between $\XX(\delta)$ and the parallel transport of $\XX(0)$.
That is, we recover the covariant derivative as $$\nabla_\theta \XX(0) = \lim_{\delta \to 0} \frac{\XX(\delta)-\psi(\delta)(\XX(0))}{\delta}.$$
Note here that it does not make any sense for the covariant derivative on the circle to be in the $\frac{\partial}{\partial r}$ direction, since that is extrinsic to the circle, and the covariant derivative gives intrinsic information only.
Now we move on to the general case.
Let $M$ be a Riemannian manifold, $g$ its metric, and $\nabla$ its connection.
The torsion-free condition specifies that for any vector fields $X$ and $Y$ on $M$, $\nabla_X\nabla_Y - \nabla_Y\nabla_X = [X,Y]$. Here $[X,Y]$ is the Lie bracket of vector fields.
To work in coordinates, fix a point $p$, and an open neighborhood $U$ of $p$ with coordinate functions $x^i$.
We denote by $\ee_i$ the $i$th tangent vector with respect to these coordinates.
The first thing we note is that $[\ee_i,\ee_j] = 0$ simply by the commutativity of the ordinary partial derivative.
We don't need any Christoffel symbol machinery to then derive that $\nabla_{\ee_j}\ee_i = \nabla_{\ee_j}\ee_i$, it is a straightforward consequence of the torsion-free condition.
Now we define the symbols $\gamma^k_{ij}$ such that $\nabla_{\ee_i}\ee_j = \gamma^k_{ij}\ee_k.$
Note here that the Christoffel symbols are the coefficients of the covariant derivative, not the ordinary derivative. Be careful with notation.
$$\frac{\partial \vec{\mathbf{e_i}}}{\partial x^j}=\Gamma^k_{ij}\vec{\mathbf{e_k}}$$
Let $\vv$ be a vector field, which is given in components as $v^i\ee_i$.
Then we have that $$\nabla_{\ee_i}\vv
= \nabla_{\ee_i}(v^j\ee_j)
= (\nabla_{\ee_i}v^j)\ee_j + v^j(\nabla_{\ee_i}\ee_j)
= \frac{\partial v^j}{\partial x^i}\ee_j + v^j\gamma^k_{ij}\ee_k.$$
Now suppose that $\vv$ is equal to $\ee_l$, so $v^l = 1$ and $v^i=0$ otherwise. We then get that
$\frac{\partial v^i}{\partial x^j} = 0$, and thus that
$$\nabla_{\ee_i}\vv = \gamma^k_{il}\ee_k
= \nabla_{\ee_i}\ee_l.$$
This is a tautology, we have recovered no new information.
Here is where you make the mistake in your derivation.
let's consider the covariant derivative of the covariant basis vector. Observe
$$\nabla_i \vec{\mathbf{e_j}} = \frac{\partial \vec{\mathbf{e_j}}}{ \partial x^i } - \Gamma^k_{ij} \vec{\mathbf{e_k}}$$
You have put here a minus instead of a plus in the right-hand side, which should read: $$= \frac{\partial \vec{\mathbf{e_j}}}{ \partial x^i } + \Gamma^k_{ij} \vec{\mathbf{e_k}}$$
Fixing this in the following steps, and using the corrected definition of Christoffel symbols, you would get:
$$ \nabla_i \vec{\mathbf{e_j}} = \frac{\partial \vec{\mathbf{e_j}}}{ \partial x^i } + \Gamma^k_{ij} \vec{\mathbf{e_k}} = \Gamma^k_{ij} \vec{\mathbf{e_k}},$$
which implies the correct result that $$\frac{\partial \vec{\mathbf{e_j}}}{ \partial x^i } = 0.$$
In general, it is true that the partial derivatives of $\ee_i$ vanish, but the covariant derivatives do not. The Christoffel symbols measure precisely by how much these differ.
Best Answer
I will proceed with Einstein summation as you have.
Let $\partial_i$ denote $\dfrac{\partial}{\partial x^i}$. Let $u^m$ be a contravector and $\mu_m$ a covector.
First note that by the product rule, \begin{align} \partial_i(\mu_m u^m) &= (\partial_i \mu_m)u^m + \mu_m(\partial_i u^m)\\ \mathrm{So\ by\ rearranging,}\quad (\partial_i \mu_m)u^m &= \partial_i(\mu_m u^m) - \mu_m(\partial_i u^m) \end{align} We now proceed by finding how $\nabla_i\mu_m$ acts on an arbitrary vector to show how it acts on all vectors. (The covariant derivative of a covector is itself a covector, i.e. a map that acts on vectors, so this is precisely what we must find out.) \begin{align} (\nabla_i\mu_m)(u^m) &= \partial_i (\mu_m u^m) - \mu_m(\nabla_i u^m)\\ &= \partial_i (\mu_m u^m) - \mu_m(\partial_iu^m + \Gamma_{ij}^m u^j) \mathrm{\quad(by\ the\ formula\ given\ in\ your\ question)}\\ &= (\partial_i\mu_m)u^m - \Gamma_{ij}^m \mu_m u^j \mathrm{\quad(by\ the\ product\ rule\ above)} \end{align} By the summation convention, we have that $(\partial_i\mu_m)u^m - \Gamma_{ij}^m \mu_m u^j = (\partial_i\mu_m)u^m - \Gamma_{ij}^p \mu_p u^j$. (As the two terms in the equation are linked by subtraction, we do not change anything by re-labelling the second $m$ index to another letter.) In the same way, we relabel the $j$ to $m$. $$(\nabla_i\mu_m)(u^m) = (\partial_i\mu_m)u^m - \Gamma_{im}^p \mu_p u^m$$ As the contravector was arbitrary, this shows that $$\nabla_i\mu_m = \partial_i\mu_m- \Gamma_{im}^p \mu_p$$