Ah I just figured it out! I was using a KVM with a "fast switching mode" where you can hit the side of the screen with your mouse twice to switch inputs. Somehow this got turned on. (It also explains why it was randomly switching inputs without me asking!)
As soon as you turn it off (Scroll lock, Scroll lock, F12 for the one I'm using), the mouse works perfectly again. My guess is that in order to know when you hit the side of the screen, the KVM has to be in charge of the position of the cursor on the screen, so it must set the mouse to absolute mode, and then the OS sensitivity has no effect.
Would be nice if something in the UI said the mouse is operating in absolute mode (I didn't even know that was possible, though I guess graphics tablets use it).