Coordinate descent updates one parameter at a time, while gradient descent attempts to update all parameters at once.
It's hard to specify exactly when one algorithm will do better than the other. For example, I was very shocked to learn that coordinate descent was state of the art for LASSO. And I was not the only one; see slide 17.
With that said, there are some features that can make a problem more amendable to coordinate descent:
(1) Fast conditional updates. If, for some reason, the problem allows one to individually optimize parameters very quickly, coordinate descent can make use of this. For example, one may be able to update certain parameters using only a subset of the data, greatly reducing computational cost of these updates. Another case is if there is a closed form solution for an individual parameter, conditional on the values of all the other parameters.
(2) Relatively independent modes for parameters. If the optimal value of one parameter is completely independent of the other parameters values, then one round of coordinate descent will lead to the solution (assuming that each coordinate update finds the current mode). On the other hand, if the mode for a given parameter is very highly dependent on other parameter values, coordinate descent is very likely to inch along, with very small updates at each round.
Unfortunately, for most problems, (2) does not hold, so it is rare that coordinate descent does well compared alternative algorithms. I believe the reason it performs well for LASSO is that there are a lot of tricks one can use to enact condition (1).
For gradient descent, this algorithm will work well if the second derivative is relatively stable, a good $\alpha$ is selected and the off-diagonal of the Hessian is relatively small compared with the diagonal entries. These conditions are rare as well, so it generally performs worse than algorithms such as L-BFGS.