Propagating spin-wave spectroscopy is reported for two-dimensional CoFeB antidot lattices (ADLs) with perpendicular-to-plane magnetization. The magnonic crystals consist of square lattices of 190 nm diameter holes with different periods p. At p = 600 nm, the velocity v g of long wavelength spin-waves is reduced compared to the unpatterned reference film by up to about 30%. However, a large v g is regained when we leave out a column of nanoholes in the ADLs. Such a magnonic crystal wave guide is found to support faster spin waves than a CoFeB stripe of the same geometrical width, making the finding interesting for spin-wave guiding in integrated magnonics.