This work considers the stability of an electro-osmotic microchannel flow with streamwise electrical conductivity gradients, a configuration common in microfluidic applications such as field amplified sample stacking. Previous work on such flows has focused on how streamwise conductivity gradients set a nonuniform electro-osmotic velocity which results in dispersion of the conductivity field. However, it has been known for many years that electric fields can couple with conductivity gradients to generate unstable flows. This work demonstrates that at high electric fields such an electrohydrodynamic instability arises in this configuration and the basic mechanisms are explored through numerical simulations. The instability is unique in that the nonuniform electro-osmotic flow sets the shape of the underlying conductivity field in a way that makes it susceptible to instability. While nonuniform electro-osmotic flow sets the stage, the instability is ultimately the result of electric body forces due to slight departure from electroneutrality in the fluid bulk. A simple stability map is created where two dimensionless numbers can predict system stability reasonably well, even though the system formally depends on six dimensionless groups.