Strange -- I cannot reproduce the problem with findutils 4.5.12 alpha, on either Fedora 20 or on Ubuntu 14.04 (both x86-64).
Stephen, can you do an 'strace' of the failing 'find' invocation? Something like this, where the files are not yet compressed:
cd "/home/shassard/opt/emacs/share/emacs/24.3.92/lisp"
strace -f -o /tmp/tr find . -name '*.elc' -exec /bin/sh -c \(/tmp/tr will be fairly large, alas) and look in /tmp/tr just before 'find' issues its first complaint.
'/usr/bin/gzip -9n `expr "$1" : "\\(.*\\)c"`' dummy '{}' ';'