This seems quite strange. 1/500 is the default speed -- purely mechanical -- and should work without a battery. All the slower speeds involve some sort of electronically controlled interaction. The electronics are in the body, and as CGW said, the shutter is in the lens. Trying another lens might help isolate the problem between lens and body. That is, it could be some sort of switch malfunction that the 1/500 setting isn't switched correctly in the body. You might try removing the battery and see if the camera fires at an obviously fast rate. If it does, that would point toward the body as the problem, if there's no difference, it suggests the lens has a problem.
It seems odd to me that a slower speed like 1/125 would work if the shutter was mechanically hanging at the1/500 setting.