The present paper looks at Matveev's complexity (introduced in 1990 and based on the existence of a simple spine for each compact 3-manifold: see [Acta Appl. Math. 19 (1990), 101-130]) through another combinatorial theory for representing 3-manifolds, which makes use of particular edge-coloured graphs, called crystallizations. Crystallization catalogue $\tilde C^{26}$ for closed non-orientable 3-manifolds (due to [Acta Appl. Math. 54 (1999), 75-97]) is proved to yield upper bounds for Matveev's complexity of any involved 3-manifold. As a consequence, an improvement of Amendola and Martelli classification of closed non-orientable irreducible and $P^2$-irreducible 3-manifolds up to complexity c=6 is obtained.