Disclaimer. I am unable to follow the proof of Theorem 5 in Shi et al. 2012.
But it is not difficult to show the following angle preservation statement based on the Tail Bound Lemma, that is, Lemma 10 of the article.
Claim. Let $\mathbf{x}, \mathbf{w} \in \mathbb{R}^d \setminus \{0\}$ and let $\mathbf{R} \in \mathbb{R}^{n, d}$ be a random Gaussian matrix as in Lemma 4 and let $\varepsilon \in (0, 1)$. Set $\cos(\beta) \Doteq \frac{\langle \mathbf{x}, \mathbf{w} \rangle}{\| \mathbf{x}\| \| \mathbf{w} \| }$ and $\cos(\beta') \Doteq \frac{\langle \mathbf{Rx}, \mathbf{Rw} \rangle}{\| \mathbf{Rx}\| \| \mathbf{Rw} \| }$. Then the following inequalities hold $$ \cos(\beta) - \frac{2 \varepsilon}{1 + \epsilon} \le \cos(\beta') \le \cos(\beta) + \frac{2 \varepsilon}{1 - \varepsilon} $$ with probability at least $1 - 6 \exp \left(-\frac{n}{2}(\frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3})\right)$.
Proof. Let $x = \|\mathbf{x}\|, w = \|\mathbf{w}\|, x' = \|\mathbf{Rx}\|$ and $w' = \|\mathbf{Rw}\|$. Set also $p_{n, \varepsilon} \Doteq 1 - 6 \exp \left(-\frac{n}{2}(\frac{\varepsilon^2}{2} - \frac{\varepsilon^3}{3})\right)$. By Lemma 10 and the union bound, the following inequalities
$(x)$ $\sqrt{1 -\varepsilon} \le \frac{x'}{x} \le \sqrt{1 + \varepsilon}$,
$(w)$ $\sqrt{1 -\varepsilon} \le \frac{w'}{w} \le \sqrt{1 + \varepsilon}$,
$(d)$ $\sqrt{1 -\varepsilon} \le \frac{\|\mathbf{R}\frac{\mathbf{x}}{x} - \mathbf{R}\frac{\mathbf{w}}{w} \|}{\| \frac{\mathbf{x}}{x} - \frac{\mathbf{w}}{w}\|} \le \sqrt{1 + \varepsilon}$,
simultaneously hold with probability at least $p_{n, \varepsilon}$. The right-most inequality in $(d)$ is equivalent to $$\left(\frac{x'}{x}\right)^2 + \left(\frac{w'}{w}\right)^2 - 2 \frac{x'w'}{xw}\cos(\beta') \le 2(1 + \varepsilon)(1 - \cos(\beta)).$$ Using then $(x)$ and $(w)$, we deduce from the above inequality that $$2(1 - \varepsilon) - 2(1 + \varepsilon)\cos(\beta') \le 2(1 + \varepsilon)(1 - \cos(\beta))$$ and hence $$\cos(\beta') \ge \cos(\beta) - \frac{2 \varepsilon}{1 + \varepsilon}$$ holds with probability at least $p_{n, \varepsilon}$. A similar reasoning with the left-most inequality in $(d)$ yields the result.