We present new observations from Z-Spec, a broadband 185-305 GHz spectrometer, of five sub-millimeter bright lensed sources selected from the Herschel Astrophysical Terahertz Large Area Survey (H-ATLAS) science demonstration phase (SDP) catalog. We construct a redshift finding algorithm using combinations of the signal-to-noise of all the lines falling in the Z-Spec bandpass to determine redshifts with high confidence, even in cases where the signal-to-noise in individual lines is low. We measure the dust continuum in all sources and secure CO redshifts for four out of five (z~1.5-3). In one source, SDP.17, we tentatively identify two independent redshifts and a water line, confirmed at z=2.308. Our sources have properties characteristic of dusty starburst galaxies, with magnification-corrected star formation rates of 10^(2-3) M_sun/yr. Lower limits for the dust masses (~a few 10^8 M_sun) and spatial extents (~1 kpc equivalent radius) are derived from the continuum spectral energy distributions, corresponding to dust temperatures between 54 and 69K. In the LTE approximation, we derive relatively low CO excitation temperatures (< 100 K) and optical depths (tau<1). Performing a non-LTE excitation analysis using RADEX, we find that the CO lines measured by Z-Spec (from J=4->3 to 10->9, depending on the galaxy) localize the best solutions to either a high-temperature / low-density region, or a low-temperature / high-density region near the LTE solution, with the optical depth varying accordingly. Observations of additional CO lines, CO(1-0) in particular, are needed to constrain the non-LTE models.