> how long should one try to make a new job work?

Depends on your mandate going in. Stick-to-itivness is a desirable leadership quality. Most industries consider business cycles in annual terms. If you can't move the needle in 24-36 months, do everyone a favor and move-on. A 3 week stint however, is not worth putting on your CV.