I don't think Python 2.x should be changed - but 3.0 or 3.1 should be:

 - Characters don't mean a thing in zlib-land, all operations are based
on bytes and their (implicit) default encoding. This behaviour is hidden
and somewhat violates the rule of least surprise.
 - type(zlib.decompress(zlib.compress('abc'))) == bytes anyway
 - Changing from s* to y* forces the programmer to use .encode() on his
strings (e.g. zlib.compress('abc'.encode()) which very clearly shows
what's happening. If you want to compress and decompress Python3
strings, you *must* share the same character encoding; think of
zlib.compress('hôńè') and str(zlib.decompress(x)) with different locales.
 - Other modules (hashlib comes to my mind...) already reject Unicode
objects for the same argument.