What is the underlying cause of this bug?

👍 LGTM

@tacaswell, the problem is that _makeline is looking only for 'color', not 'c', when deciding whether to assign a color from the color_cycle. So if 'c' is there, it doesn't see it, and it goes ahead and adds a 'color' kwarg. Then Line2D sees both. I haven't looked to see what goes on there, but based on the user reports, whether 'c' or 'color' takes precedence varies with the Python version. It's probably a matter of the lack of order preservation in dictionaries. Maybe the hash function is version-dependent.
It would be possible to put the alias substitution in _makeline, but it seems more robust to put it in plot. All sorts of variations on the theme are possible; we could warn or raise if a 'c' clobbers a 'color', for example. But is handling that case worth the extra LOC at this point?

This all goes back to http://bugs.python.org/issue13703 which added seed randomization to the hash function used in dictionaries to prevent DoS attacks on web-frameworks. Turning this randomization on was available, but off by default in 2.7 -> 3.2 and on by default in >3.3.

The fact that we are seeing these bug reports bodes well for python 3 uptake in the scientific world :).

back-ported as 3f03e2e