You must complete them all before the new quests are available. It ties them all together, which is why the rest need to be completed.

MSQ will never need you to level multiple jobs.