Swimming cells often have to self-propel through fluids displaying non-Newtonian rheology. While past theoretical work seems to indicate that stresses arising from complex fluids should systematically hinder low-Reynolds number locomotion, experimental observations suggest that locomotion enhancement is possible. In this paper we propose a physical mechanism for locomotion enhancement of microscopic swimmers in a complex fluid. It is based on the fact that microstructured fluids will generically phase-separate near surfaces, leading to the presence of low-viscosity layers, which promote slip and decrease viscous friction near the surface of the swimmer. We use two models to address the consequence of this phase separation: a nonzero apparent slip length for the fluid and then an explicit modeling of the change of viscosity in a thin layer near the swimmer. Considering two canonical setups for low-Reynolds number locomotion, namely the waving locomotion of a two-dimensional sheet and that of a three-dimensional filament, we show that phase-separation systematically increases the locomotion speeds, possibly by orders of magnitude. We close by confronting our predictions with recent experimental results.