I don't know whether or not this would help but, me and my friend 1st launch Halo CE with the desired difficulty in solo. Right after the cutscene ends, wait a while and then exit the game, going back to the lobby. We then join each other, launch Halo CE on the desired difficulty, which in this case was legendary, and everything was working fine. Though we could not activate any skull with this method. Our take on this is the game needs something like an existing cache for the Halo CE campaign in order for the co-op to be able to run.