I believe the following simple algorithm is $O(n\log k)$-time, but I can't prove it because the subproblems are not guaranteed to stop on level $\log k$ of the recursion -- counterexamples, suggestions or direct edits welcome!
Splitting purple intervals
The basic idea is that we maintain a set of intervals containing both red and blue points (I'll call these purple intervals), initially consisting of a single interval containing all the points, and for as long as this set is not empty, we remove some interval from it, split it in half, and add back in whichever of these two halves are still purple (this may be 0, 1 or 2 intervals). Intervals generated along the way that contain only red or only blue points don't need to be subdivided further, and by the time no purple intervals are left, they partition the input into at least $k+1$ blocks of same-coloured points, from which the solution can be read off in $O(n)$ time.
By maintaining for each interval the list of points in that interval, an interval containing $m$ points can be split into two halves each containing at most $\lceil m/2 \rceil$ points in $O(m)$ time using the linear-time "median of medians" algorithm for finding medians. We can also determine in $O(m)$ total time whether each half is red, blue or purple: Loop over the $m$ points, incrementing one of four counters ($<$ median and blue, $<$ median and red, $\ge$ median and blue, $\ge$ median and red) for each. The lists of points for the two halves can be created in the same loop.
The splitting process can be represented as a binary tree, with nodes representing intervals and coloured red, blue or purple. The root node consists of the interval containing all points. Purple nodes have 0, 1 or 2 purple children, with the remaining children being red or green leaves that together partition the input points. All intervals on level $i$ have size $n/2^i$ and are disjoint; since a purple node implies at least one red-blue or blue-red colour change, there can be at most $k$ purple nodes on any level. I think this constraint is important for obtaining an $O(n\log k)$ time bound, but haven't figured out how to make use of it.