How is it that angular velocities are vectors, while rotations aren't?

There are actually several different ways to interpret that question, depending on what you mean by "vector" and "rotation". But here's a sense that I've often wondered about myself: in introductory physics, the velocity vector is defined as the time derivative of the position vector (relative to some fixed point). Why is the same not true of angular velocity - that is, why isn't there an "angular position vector" which angular velocity can be the derivative of?

As a matter of fact, sometimes there is. Think about this simple case: pick a single, fixed rotation axis and only consider rotations about that axis. (2D rotations, if you prefer to think of it that way) You'd pick a certain orientation to be the "origin," and you could actually define an angular position vector, pointing along the rotational axis, with length equal to the amount of rotation relative to that "origin" orientation.

Now, suppose your object's angular position is changing over time. You can take the derivative of the angular position vector, and hopefully you can see that what you'd get is just the good old angular velocity. No problem there.

But we live in a 3D world (relativity notwithstanding), so what happens when you try to generalize that model to 3 dimensions? That's where you run into problems. As an example, take the object from the last paragraph, which was rotating around one particular axis - say, the $\hat{z}$ axis. Now suppose it changes its motion so that it starts rotating around a different axis, maybe the $\hat{x}$ axis. How will you represent its orientation now?

You might be tempted to use an "angular position vector" pointing in the $\hat{z}$ direction, whose length represents the amount of rotation around the $\hat{z}$ axis, and another "angular position vector" pointing in the $\hat{x}$ direction, whose length represents the amount of rotation around the $\hat{x}$ axis. After all, that works for position. But it doesn't work for angular position. The reason why is that rotations do not commute, to use the technical lingo. What that means is that if you apply rotation A to an object and follow it up by rotation B which is around a different axis, you get a different result than if you apply rotation B followed by rotation A.

This little issue gets in the way if you try to combine your two $x$- and $z$- angular position vectors into one overall angular position vector. Presumably, you would write this overall vector as $(\theta_x, 0, \theta_z)$ (the zero might represent the amount of rotation around the $\hat{y}$ axis). That vector would represent the sum of $\theta_x$ times the unit rotation around the $\hat{x}$ direction and $\theta_z$ times the unit rotation around the $\hat{z}$ direction. But it's missing a critical piece of information: which of those rotations was performed first? If you gave that vector to your physicist friend, he would be unable to reproduce the orientation of the object because he doesn't know whether to perform the $x$-rotation or the $z$-rotation first. Sure, you may know that the object was rotated in the $z$-direction first, but that information needs to be contained in the vector for it to be of any use.

The point of the last paragraph is that there's no way to sensibly create linear combinations of these "angular position vectors." And that pretty much ruins their usefulness, because the ability to be linearly combined is absolutely fundamental to the definition of a vector, and it underlies a lot of the analytical techniques we use in physics.

By the way, in this view, the reason matrices work to represent rotations is that matrices offer you an additional operation, multiplication, which you can use to combine them. It happens that matrix multiplication, for certain matrices (3x3 antisymmetric with determinant 1), has the same properties as composing rotations; most notably, it's also noncommutative. Multiplying matrix A by matrix B can give you a different result from multiplying matrix B by matrix A.

This is a note on why angular velocities are vectors, to complement Matt and David's excellent explanations of why rotations are not.

When we say something has a certain angular velocity $\vec{\omega_1}$, we mean that each part of the thing has a position-dependent velocity

$\vec{v_1}(\vec{r}) = \vec{\omega_1} \times \vec{r}$.

We might consider another one of these motions

$\vec{v_2}(\vec{r}) = \vec{\omega_2} \times \vec{r}$

and wonder what happens when we add them. We get

$\vec{v_1}(\vec{r}) + \vec{v_2}(\vec{r}) = \vec{\omega_1} \times \vec{r} + \vec{\omega_2} \times \vec{r}$.

The cross product is linear, so this is equivalent to

$(\vec{v_1} + \vec{v_2})(\vec{r}) = (\vec{\omega_1} + \vec{\omega_2}) \times \vec{r}$,

so it makes fine sense to add angular velocities by vector addition.

Defining properties of vectors are that you can add them and multiply them by constants. These both make sense for angular velocities. On the other hand, adding rotations doesn't make sense. What you can do with two rotations is compose them: first rotate one way, then rotate another. This operation doesn't look like addition of any sort. For one thing, it doesn't commute. Rotating something $30$ degrees around the $x$-axis, then $60$ degrees around the $y$-axis, is not the same thing as doing those two operations in the opposite order. (If you've never done so, pick up an object and try!) So the mathematical operation that corresponds to rotations has to be something that is able to express noncommutativity. Matrices work very naturally for this; for two matrices A and B, it isn't true in general that $AB = BA$.