4 white balls and 1 black ball, choose two with replacement, probability of drawing 2 black balls? So I have 2 answers that I think both makes sense, but one has to be wrong.
$\textbf{Solution 1:}$
Choose a ball, the chance that it's black is $\frac{1}{5}$. Put it back and choose another one, with probability $\frac{1}{5}$ that it's going to be black again. So both of these event happens with probability 
$$\frac{1}{5} \times \frac{1}{5} = \frac{1}{25}.$$
$\textbf{Solution 2:}$
This is choosing $k$ items from a set of $n$ objects with replacement. The number of ways this can happen is given by the stars and bars argument ${n+k-1 \choose k}$. So in our case, we have 
$$\frac{1}{{5+2-1 \choose 2}} = \frac{1}{15}.$$
Which one is correct and why?
 A: Let us look at a smaller example so that I can highlight what exactly went wrong.
Suppose we have a bag with three balls: $1$ is red, $1$ is green, and $1$ is black.  We choose two balls independently with replacement and we ask what is the probability that both balls we drew were black.
So that we are perfectly clear as to what is going on, we draw one ball and record what it was, put it back, and then draw again.  The choice of the ball in the first draw in no way affects the choice of the ball in the second draw.  There is a very clear distinction between which ball was drawn first versus second in the process (though we may forget about which order they came in if we so choose but it is helpful not to).
We have the following nine possibilities:
$$\begin{cases} RR&RG&RB\\GR&GG&GB\\BR&BG&BB\end{cases}$$
Each of these nine possibilities are equally likely to occur, by the assumption of , and so the probability of getting a black ball each time is $\frac{1}{9}$, the number of favorable occurrences divided by the number of possible outcomes.
Had we gone with the stars and bars formula to describe the number of elements in our sample space, letting $(r,g,b)$ represent the triple denoting how many red balls, green balls, and black balls we received each respectively we would have ended with the sample space: 
$$\begin{cases} (2,0,0)&(1,1,0)&(1,0,1)\\&(0,2,0)&(0,1,1)\\&&(0,0,2)\end{cases}$$
Notice however, that the outcome $(2,0,0)$ corresponds only to the outcome $RR$, however the outcome $(1,1,0)$ corresponds to the outcome $RG$ as well as $GR$.  There are two ways that $(1,1,0)$ can have occurred, but only one way that $(2,0,0)$ could have occurred.
So, although there are $6$ outcomes in this sample space, not all six of them occur equally often so we may not use counting principles to calculate the probability with this sample space.
The same thing happens with the coin flipping example, flipping a coin four times in a row, one could say there are "five outcomes": zero tails (and four heads), one tail (and three heads), two tails (and two heads), three tails (and one head), or four tails, but we should know that the probability of three tails in a row is $\frac{1}{16}$, not $\frac{1}{5}$

For your specific problem, it is easiest to approach directly using probability arguments that the answer should be $\frac{1}{5}\cdot \frac{1}{5}$, but if you wanted to use a counting principle argument, the first step would be to define a sample space in which every outcome is equally likely to occur.
For this to occur, we may temporarily assume that the white balls are all labeled (because the white balls having or not having some special markings on them won't change the probability that they are drawn).  Let the four white balls be labeled $W_1,W_2,W_3,W_4$ and the black ball be labeled $B$.
We have the equiprobable sample space then with $25$ outcomes:
$$\begin{cases}W_1W_1&W_1W_2&W_1W_3&W_1W_4&W_1B\\W_2W_1&W_2W_2&\dots\\
\vdots\\
&&&&\cdots BB\end{cases}$$

"I'm trying to understand when I can use the stars and bars argument"
You generally can't unless the problem very specifically states that we are randomly choosing one of the possible outcomes described by the stars and bars setup uniformly at random.
For example: "What is the probability that a uniformly randomly selected integer triple $(x_1,x_2,x_3,x_4,x_5)$ satisfying $\begin{cases}x_1+x_2+x_3+x_4+x_5=2\\0\leq x_i~~\forall i\end{cases}$
has $x_5=2$?"
