The way micro-organisms swim in concentrated polymer solutions has important biomedical implications, e.g. in understanding how pathogens invade the mucosal lining of our guts. Physicists are also fascinated by self-propulsion in such complex, `non-newtonian’ fluids. The current model `standard model’ of how bacteria propelled by rotary helical flagella swim through concentrated polymer solutions postulates bacteria-sized `pores’, allowing them relative easy passage. Using new, high-throughput methods for characterising bacterial motility, we have measured the swimming speed and the angular frequency of cell-body rotation of Escherichia coli in polyvinylpyrollidone (PVP) and Ficoll solutions of different molecular weights. Our results overturn the `standard model’. We found two distinct behaviors in Newtonian and Non-Newtonian solutions. Results at low molecular weight can be explained by Newtonian hydrodynamic theory, which brings about striking data collapse at different molecular weights. For the highest molecular weight, we observed a scaling failure between the swimming speed and angular velocity not explained by such theory and presumably due to Non-Newtonian effect.