Ball collision problems

So I have a system with colliding balls that generally works, except for when they collide with similar directions, less than 90 degrees apart.

This is because the ball above tries to collide against the yellow line which is supposedly the collision plane, but it sends it off the wrong direction, and it "follows" the other ball. The general algorithm for the collision is:

dot = direction.surface;
parallel = surface * dot;
perpendicular = direction - parallel;
direction = perpendicular - parallel;

Which negates the component of the direction parallel to the surface normal, which is perpendicular to the collision plane, and the part perpendicular to the surface normal is unchanged.

Does anyone know a fix for this? Have I done something wrong?

Edit: So now I added:

average = (ball1.velocity + ball2.velocity) / 2;
ball1.velocity -= average;
ball2.velocity -= average;

Before doing the calculations above, and after that:

ball1.velocity += average;
ball2.velocity += average;

To get in the right reference frame, according to @Beta's answer. The problem now is that the speeds of the balls aren't maintained, since they both have the same speeds and masses, yet after the collisions they're different. I do not think this is supposed to happen, or is it?

Consider the 1D problem of bouncing a ball off a wall. Simple.

Now watch me bounce a ball off the forward bulkhead of a jet plane in flight. The ball is moving north at 252 m/s, the bulkhead is moving north at 250 m/s. The answer is not obvious. But shift into my coordinate frame (by subtracting the velocity of the bulkhead, 250 m/s, from everything) and the problem is trivial. Solve it, then shift the result back into the ground frame (by adding 250 m/s to everything) and you're done.

Now the 2D problem of a ball bouncing off a wall at an angle. Simple. (But verify that your code does it correctly.)

Now two balls colliding with equal and opposite momenta (I'll assume they have the same mass, for now). You can imagine a yellow wall at the collision plane, and the answer comes easily.

Now two balls colliding, but with velocities that do not add up to zero. There's still a yellow wall, but it's moving. Well, shift into the wall's frame by subtracting the average of the balls' velocities (sum/2) from everything, solve the simpler problem, then shift back by adding that same velocity back to everything, and you're done.