Por lo que mencionas... me parece que el archivo PDF en sí mismo es el que ha sido protegido y no te permitirá imprimir (seguramente tampoco puedas copiar), algunas personas protegen sus archivos PDF para que solamente puedan servir como lectura, pero que no puedan ser impresos ni tampoco se pueda copiar de ellos; Esa es la razón por la que no puedes imprimir ese archivo y sí los que tu creas.
Para Linux no conozco ningún programa, pero si tienes otra compu con Windows te recomiendo el PDF Password Remover v2.5 o superior. Le ejecutas, abres el PDF y luego te pide que lo guardes ya sin restricciones.
Saludos.