I guess there are three questions here.
- Is every question involving randomness a probability question?
Obviously not (e.g., imagine a story involving people gambling with dice, where the randomness is just there as scenery), but I think any question about randomness is a probability question, at least if it's quantitative about it. "Mathematical puzzle that involves randomness" isn't too far off, it seems to me.
The "equal partial sums" question linked by boboquack is indeed not a probability question, but boboquack has correctly diagnosed the real problem there: the title uses the word "random" but doesn't really mean "random". I think this question is largely irrelevant to the point at issue.
- Does every probability question involve randomness?
Maybe not, for two reasons. Firstly, sometimes you use probabilistic methods to solve a not-obviously-probabilistic question (e.g., you want to prove that a Thing with a certain Property exists, and you do it by saying "Consider a randomly chosen Thing; then the probability that it has the Property is at least such-and-such, which is bigger than 0; therefore at least one Thing exists with that Property"). But these probably shouldn't be considered probability questions in our sense.
Secondly, the techniques of probability theory are applicable whenever we have uncertainty, whether or not there is actual randomness. So if I want to decide whether my wife is having an affair, or whether some religion's claims are true, I might do it by making an initial assignment of probabilities and then updating according to the available evidence using Bayes' theorem. But questions of this sort where the uncertainty doesn't come from quantifiable sources of randomness are likely not to have definite answers and therefore not to be suitable for Puzzling.
- Do the observations above mean there's a problem with how the probability tag is described?
I don't think they do. The objections above are all quibbles, in this context. Unless we have actual examples of questions that are being misclassified and would be classified better if we had a different definition for the tag, I think it's fine.