Parece que você deveria ter usado o tar (com a opção gzip):
# -z : pipe through gzip
# -cf : create file
tar -zcf new.tgz /path-to-directory
depois com o arquivo new.tgz resultante:
# z : gzip
# x : extract
# p : keep permissions
tar zxpf new.tgz
EDITAR
Qual é o objetivo do gzip -r então? - jeffp 37 minutos atrás
O gzip é um compressor de fluxo - ele realmente não olha para o conteúdo do que você está compactando além do que ele precisa para torná-lo menor, então ele não tem nenhum conceito de diretórios.
Assim como uma nota lateral, acho que o bzip2 faz um trabalho muito melhor de compactação do que o gzip - embora seja mais lento.
# -j : pipe through bzip2
# -cf : create file
tar -jcf new.tar.bzip2 /path-to-directory
bunzip2 new.tar.bzip2