T-duality acts on circle bundles by exchanging the first Chern class with the fiberwise integral of the H-flux, as we motivate using E_8 and also using S-duality. We present known and new examples including NS5-branes, nilmanifolds, Lens spaces, both circle bundles over RP^n, and the AdS^5 x S^5 to AdS^5 x CP^2 x S^1 with background H-flux of Duff, Lu and Pope. When T-duality leads to M-theory on a non-spin manifold the gravitino partition function continues to exist due to the background flux, however the known quantization condition for G_4 fails. In a more general context, we use correspondence spaces to implement isomorphisms on the twisted K-theories and twisted cohomology theories and to study the corresponding Grothendieck-Riemann-Roch theorem. Interestingly, in the case of decomposable twists, both twisted theories admit fusion products and so are naturally rings.