We present new observations from Z-Spec, a broadband 185-305 GHz spectrometer, of five submillimeter bright lensed sources selected from the Herschel-Astrophysical Terahertz Large Area Survey science demonstration phase 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 102 - 3 M &sun; yr-1. Lower limits for the dust masses (~ a few 108 M &sun;) and spatial extents (~1 kpc equivalent radius) are derived from the continuum spectral energy distributions, corresponding to dust temperatures between 54 and 69 K. In the local thermodynamic equilibrium (LTE) approximation, we derive relatively low CO excitation temperatures (lsim 100 K) and optical depths (τ <~ 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.