Yep, the key is that v and a are vectors. Try this:
1. Draw a circle with vector v's tail end on the circle and v tangent to the circle.
2. Picture v moving around the circle at constant speed.
3. Consider v at a position, v0.
4. A very short time later (dt), v moves to a new position v1 so v1 forms a small angle with v0.
5. To get dv (=v1-v0), move the tail of v1 to the tail of v0 while keeping the angle between them constant.
6. Construct a small vector with the tail at the tip of v0 and the tip at the tip of v1. This is dv.
7. It should be clear that dv is perpendicular to v.
8. Since dv occurs over the time dt, dv/dt = a is in the same direction as dv.
Hope this helps.