This is a fairly straight forward problem. Although there is a connection between the Poisson and Negative Binomial distributions, I actually think this is unhelpful for your specific question as it encourages people to think of negative binomial processes. Basically, you have a series of Poisson processes:
$$Y_i(t_i)|\lambda_i\sim Poisson(\lambda_i t_i)$$
Where $Y_i$ is the process and $t_i$ is the time you observe it, and $i$ denotes the individuals. And you are saying that these processes are "similar" by tying the rates together by a distribution:
$$\lambda_i\sim Gamma(\alpha,\beta)$$
On doing the integration/mxixing over $\lambda_i$, you have:
$$Y_i(t_i)|\alpha\beta\sim NegBin(\alpha,p_i)\;\;\; where \;\;p_i=\frac{t_i}{t_i+\beta}$$
This has a pmf of:
$$Pr(Y_i(t_i)=y_i|\alpha\beta) = \frac{\Gamma(\alpha+y_i)}{\Gamma(\alpha)y_i!}p_i^{y_i}(1-p_i)^\alpha$$
To get the waiting time distribution we note that:
$$Pr(T_i\leq t_i|\alpha\beta)=1-Pr(T_i> t_i|\alpha\beta)=1-Pr(Y_i(t_i)=0|\alpha\beta)$$
$$=1-(1-p_i)^\alpha=1-\left(1+\frac{t_i}{\beta}\right)^{-\alpha}$$
Differentiate this and you have the PDF:
$$p_{T_i}(t_i|\alpha\beta)=\frac{\alpha}{\beta}\left(1+\frac{t_i}{\beta}\right)^{-(\alpha+1)}$$
This is a member of the generalized Pareto distributions, type II. I would use this as your waiting time distribution.
To see the connection with the Poisson distribution, note that $\frac{\alpha}{\beta}=E(\lambda_i|\alpha\beta)$, so that if we set $\beta=\frac{\alpha}{\lambda}$ and then take the limit $\alpha\to\infty$ we get:
$$\lim_{\alpha\to\infty}\frac{\alpha}{\beta}\left(1+\frac{t_i}{\beta}\right)^{-(\alpha+1)}=\lim_{\alpha\to\infty}\lambda\left(1+\frac{\lambda t_i}{\alpha}\right)^{-(\alpha+1)}=\lambda\exp(-\lambda t_i)$$
This means that you can interpret $\frac{1}{\alpha}$ as an over-dispersion parameter.