Eu testei o arquivo de amostra com o Adobe Reader para OS X e, embora você não tenha fornecido uma senha, Ele solicitou um, enquanto Preview.app apenas exibiu uma página em branco. (E faria sentido que o Adobe Reader para OS X fornecesse a mesma funcionalidade que o Adobe Reader para Windows).
Editar: Acabei de criar um PDF de teste criptografado AES de 256 bits com o Acrobat Pro no Windows, tentei abri-lo com o Adobe Reader no OS X e ele foi bem-sucedido.
Editar 2: Acabei de instalar o Adobe Reader 9.3.3 na minha instalação do Xubuntu e ele poderia abrir o mesmo PDF criptografado AES. Quanto ao estoque do Ubuntu, há um bug para o Evince (o renderizador PDF) tentar e obter suporte AES.