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)$.