We discuss the relation between spacetime diffeomorphisms and gauge transformations in theories of the Yang-Mills type coupled with Einsteins General Relativity. We show that local symmetries of the Hamiltonian and Lagrangian formalisms of these generally covariant gauge systems are equivalent when gauge transformations are required to induce transformations which are projectable under the Legendre map. Although pure Yang-Mills gauge transformations are projectable by themselves, diffeomorphisms are not. Instead the projectable symmetry group arises from infinitesimal diffeomorphism-inducing transformations which must depend on the lapse function and shift vector of the spacetime metric plus associated gauge transformations. Our results are generalizations of earlier results by ourselves and by Salisbury and Sundermeyer.