I'm trying to rotate a 4 dimensional point (w,x,y,z). So far I've been rotating around planes (wx,xy,yz,zw,wy, and xy), but the order in which I do these rotations changes the results and can sometimes result in gimbal lock.
I understand that quaternions are the solution to this problem in 3 dimensions, but can quaternions also do rotations in 4 dimensions and if so, how?
As Jyrki suggests, it is possible to use a pair of unit quaternions to describe a rotation is four dimensions. Specifically, any rotation $R$ can be written as $$ R(v) \;=\; avb $$ where $v$ is a vector in $\mathbb{R}^4$ (treated as a quaternion), and $a$ and $b$ are the unit quaternions describing the rotation.
Given two such rotations $$ R(v) \;=\; avb \qquad\text{and}\qquad R'(v)\;=\;a'vb' $$ the composition $R\circ R'$ (i.e. rotating $R'$ and then rotating $R$) is obtained by multiplying the corresponding quaternions: $$ (R\circ R')(v) \;=\; (aa')v(b'b). $$
Rotations around the six coordinates planes can be described as follows: $$ \begin{array}{cc} R_{wx}^\theta(v) \;=\; e^{-i\theta/2}ve^{i\theta/2} & R_{yz}^\theta \;=\; e^{i\theta/2}ve^{i\theta/2} \\ \\ R_{wy}^\theta(v) \;=\; e^{-j\theta/2}ve^{j\theta/2} & R_{xz}^\theta \;=\; e^{j\theta/2}ve^{j\theta/2} \\ \\ R_{wz}^\theta(v) \;=\; e^{-k\theta/2}ve^{k\theta/2} & R_{xy}^\theta \;=\; e^{k\theta/2}ve^{k\theta/2} \end{array} $$ where $e^{j\theta} \;=\; \cos(\theta) + j\sin(\theta)$, etc.
Finally, note that the quaternion-pair representation of a rotation is not unique. Specifically, the rotation with coefficients $(a,b)$ is the same as the rotation with coefficients $(-a,-b)$, for all unit quaternions $a$ and $b$.