I know on the beginner's westside program, it changes every three weeks. The guys at westside change every week, but they use a lot more weight, too.
We change our primary exercise every two to three weeks. You have to give your body a chance to adapt to the new exercise, and a chance to get your form right.
My training partner and I have found that fixing form issues is just as important as the strength end of it. So I'd say probably three weeks to start out.