Ah, yep I see the race. Here is a fix: https://gist.github.com/sdab/d7ba036b2b7f4b5626cd
Thanks for the puzzle, its hard to find good concurrency problems.
Edit: Looked through your solution. You are right, we thought of similar things. I started out by wanting a multi condition variable, but didnt want to implement it :). I ended up getting something similar in a roundabout way.
I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html
I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).