So, if you know the password for a PDF and want to remove it, you can use the command line tools pdftops and ps2pdf to free your PDF from its chains.
Install pdftops. On Ubuntu, you can do:
apt-get install xpdf-utils
Install ps2pdf. I think this is already included with a default Ubuntu.
Convert the PDF to a postscript file, using the password:
pdftops -upw <password> <file>.pdf
Convert the resulting postscript (which is now sans password) back to a PDF:
The only thing you lose are any PDF-specific features which don’t translate to postscript, e.g. hyperlinks.
Remember, this only works if you know the password for the PDF: it doesn’t break the PDF password for you.