Well, my bad. Had the Atmel-ICE programmer cable in backwards. I guess the red stripe on the cable does not correspond to the white dot on the Arduino Zero PCB. Go figure.
When you say you had it in backwards, are you referring to the way you had the connector oriented when plugging it into the Zero? Or which end of the cable you had plugged into the ICE itself? The way you worded it it sounds half like the former and half the latter.In any case, it matters which end of the ribbon cable you have plugged into the ICE programmer. The end you should be programming with is the one that also has the 6 pin ISP connector. The end without the ISP connector is the one that goes into the ICE itself. I designed my Neutrino boards to have the same pinout as the Zero, and the pin 1 dot matches up with the red stripe. But if you plugged that cable into the programmer backwards then it would not.