Let $P(k, r)$ be defined by recursion as follows: $$P(0, r) = 1$$ $$P(k + 1, 0) = 0$$ $$P(k + 1, r + 1) = \frac{k + 1}{n} P(k, r) + \left( 1 - \frac{k + 1}{n} \right) P(k + 1, r)$$ That is, $P(k, r)$ is the probability of seeing a particular set of $k$ different outcomes in $r$ samples. Note that by expanding only the second term of the second equation, we get: $$P(k + 1, r + 1) = \sum_{s = 0}^{r} \left( 1 - \frac{k + 1}{n} \right)^s \frac{k + 1}{n} P(k, r - s)$$ In particular, $$P(1, r) = 1 - \left( 1 - \frac{1}{n} \right)^r$$ as expected, and one can check that $$P(k, r) = \sum_{l=0}^{k} (-1)^l \frac{k!}{(k-l)! l!} \left(1 - \frac{l}{n}\right)^r$$ solves the recurrence.
The probability you are interested in is $P(n, r)$ – or more precisely, what you want to know is what the least number $r$ such that $P(n, r) \ge p$ is. Unfortunately to answer that question would require detailed knowledge about the asymptotics of $P(n, r)$, which seems difficult in general. For $n = 2$ things are easy, because in that case we just need to solve $$1 - \frac{1}{2^{r-1}} \ge p$$ and so we need $r \ge 1 - \log_2 (1-p)$.