It is widely believed that the swimming speed, v, of many flagellated bacteria is a nonmonotonic function of the concentration, c, of high-molecular-weight linear polymers in aqueous solution, showing peaked v(c) curves. Pores in the polymer solution were suggested as the explanation. Quantifying this picture led to a theory that predicted peaked v(c) curves. Using high-throughput methods for characterizing motility, we measured v and the angular frequency of cell body rotation, Ω, of motile Escherichia coli as a function of polymer concentration in polyvinylpyrrolidone (PVP) and Ficoll solutions of different molecular weights. We find that nonmonotonic v(c) curves are typically due to low-molecular-weight impurities. After purification by dialysis, the measured v(c) and Ω(c) relations for all but the highest-molecular-weight PVP can be described in detail by Newtonian hydrodynamics. There is clear evidence for non-Newtonian effects in the highest-molecular-weight PVP solution. Calculations suggest that this is due to the fast-rotating flagella seeing a lower viscosity than the cell body, so that flagella can be seen as nano-rheometers for probing the non-Newtonian behavior of high polymer solutions on a molecular scale.