I would try to approach your original problem a bit differently. Note that $|x-a|\le \frac 12(r|x-a|^2+r^{-1})$ and the equality is attained for $r=|x-a|^{-1}$. Thus, $$ \min_x[|x-a|+\langle b,x\rangle]=\frac 12\min_r\min_x[r|x-a+r^{-1}b|^2+r^{-1}(1-|b|^2)]+\langle a,b\rangle $$ However, the inner minimum can be now found rather quickly and finding the outer one is a one-dimensional problem. Moreover, I suspect that even the naive algorithm of choosing $r$ arbitrarily to start with, finding the corresponding $x$, and then changing $r$ to something stupid like $(|x-a|^{-1}+r)/2$ has a decent chance to work but checking that would require some accurate analysis of the properties of the inner minimum as a function of $r$. What is true, however, is that if the minimizer $x$ for some $r$ satisfies $|x-a|=r^{-1}$, then you have the true minimum for the original expression, so, at least, you can recognize the solution when you see it this way.
Edit:
I thought it might make sense to add a few more remarks to what I wrote already.
Let's look at what we have so far and see if we can convert it into something that is guaranteed to work. Put $\rho=r^{-1}$. Then the main idea was to observe that instead of the original minimization problem, we can solve the problem $$ \Psi(x,\rho)=\frac 12\left[\frac{|x-a|^2}\rho+\rho\right]+\langle b,x\rangle\to\min $$ and that in this new problem the minimization in $x$ is equivalent to finding the closest point to $a-\rho b$.
Since $\Psi$ is jointly convex in $x,\rho$ and the best $\rho$ has physical meaning of the distance from $a$ to $x$, the outer minimization problem is just the problem of finding the minimum of a convex function over a finite interval of length about the diameter of the convex body $C$ we project upon, so, even if the iterations fail, we can always resort to the good old bisection, which is guaranteed to give us the answer with the precision about $2^{-m/2}|b|\operatorname{diam} C$ where $m$ is the number of steps.
This is not an "exact" solution, of course. However, if you implement an exact algorithm on any real machine, you'll still never be able to get anything better than the machine precision. So, I'm not really sure how much sense the request for an exact solution makes here from the purely practical viewpoint. Still, notice that the closest point to $a-\rho b$ moves along a straight line as long as we stay in the relative interior of the same $k$-dimensional face of the simplex. Unfortunately, this gives us exponentially many lines, so just tracing all of them is impractical. However, we can always first run the bisection for a while until we reduce the situation to a sufficiently small interval, after which we can use only the lines that correspond to the points on that interval and, in principle, we can try to trace them. The ideal scenario is that after a few iterations in the bisection, we get the values of $x$ lying in the relative interior of the same $k$-dimensional face for both endpoints of the remaining interval, in which case we have just one line left and we can finish in a single step. It is not guaranteed to always happen, of course, but I suspect that it may work more often than not.