There are at least three ways to do this in Ubuntu. You will need the packages ghostscript (for all methods, but installed by default) and pdftk (for method 2), and optionally a Java Runtime Environment (for method 3).
Method 1: ps2pdf
The ps2pdf script that comes with Ghostscript is meant to convert PostScript to PDF, but it will happily take PDF-files as input. Just try: ps2pdf input.pdf output.pdf