Z certainly is common in Polish (particularly when including the diacritics Ź and Ż; the combinations CZ and SZ contribute a great deal), but E is much more common still, even if you don't count the Ę with it. Brian, I guess (or even bet) you have fallen victim to an urban legend.

There are better reasons to study Polish than to answer such questions. (Not that I'm really good at it, though.)