In 2.x, if you look at the docs for time.strftime, they don't even mention %z. It's not guaranteed to exist at all, much less to be consistent across platforms. In fact, as footnote 1 implies, it's left up to the C strftime function. In 3.x, on the other hand, they do mention %z, and the footnote that explains that it doesn't work the way you'd expect is not easy to see; that's an open bug.
However, in 2.6+ (including all 3.x versions), datetime.strftime is guaranteed to support %z as "UTC offset in the form +HHMM or -HHMM (empty string if the the object is naive)." So, that makes for a pretty easy workaround: use datetime instead of time. Exactly how to change things depends on what exactly you're trying to do — using Python-dateutil tz then datetime.now(tz.tzlocal()).strftime('%z') is the way to get just the local timezone formatted as a GMT offset, but if you're trying to format a complete time the details will be a little different.
If you look at the source, time.strftime basically just checks the format string for valid-for-the-platform specifiers and calls the native strftime function, while datetime.strftime has a bunch of special handling for different specifiers, including %z; in particular, it will replace the %z with a formatted version of utcoffset before passing things on to strftime. The code has changed a few times since 2.7, and even been radically reorganized once, but the same difference is basically there even in the pre-3.5 trunk.