Phononic crystals (PCs) consist of a periodic arrangement of inclusions in a matrix material, and have garnered a great deal of interest owing to a phenomenon known as band gap frequencies in which particular frequency ranges are not able to propagate through the PCs. The aim of this work is to study the effects of magneto-elastic coupling and other parameters such as randomness in geometrical properties, volume fraction and size of inclusions on longitudinal wave propagation and, in particular, on the appearance of stop-band frequencies. The results indicate that the most important parameters deciding whether a frequency is in a stop-band or a pass-band are the randomness in geometrical properties and piezomagnetic coupling. It was observed that piezomagnetic coupling can lead to a widening of the first stop-band range for a periodic microstructure. Moreover, while randomness in particle size leads to a stop-band range and reduced wave transmission in the second pass region, randomness in particle position leads to removal of the pass band ranges compared to periodic structures. Additionally, the influence of piezomagnetic coupling becomes insignificant in fully random structures.