Found this in the ubuntu forums :

 # gs -sDEVICE=pdfwrite -dCompatibilityLevel=<VERSION> -dPDFSETTINGS=/screen -dNOPAUSE -dQUIET -dBATCH -sOutputFile=output.pdf input.pdf

Just tested this and it works fine, I'll post some output now.

[14:08:41]lee@barlow:~/superuser # pdfinfo org_1-4.pdf 
Title:          CV 2009
Producer:       Prince 7.0 alpha 16 (www.princexml.com)
Tagged:         no
Pages:          3
Encrypted:      no
Page size:      595 x 842 pts (A4)
File size:      51793 bytes
Optimized:      no
PDF version:    1.4
[14:08:59]lee@barlow:~/superuser # gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.5 -dPDFSETTINGS=/screen -dNOPAUSE -dQUIET -dBATCH -sOutputFile=out_1.5.pdf org_1-4.pdf
[14:09:35]lee@barlow:~/superuser # pdfinfo out_1.5.pdf 
Producer:       GPL Ghostscript 8.64
CreationDate:   Wed Aug 19 14:09:34 2009
ModDate:        Wed Aug 19 14:09:34 2009
Tagged:         no
Pages:          3
Encrypted:      no
Page size:      595 x 842 pts (A4)
File size:      60658 bytes
Optimized:      no
PDF version:    1.5

Looking up the ghostscript options instead of blindly copying commands from others who also blindly copied their commands (and so on) is time well spent. For instance, the -dPDFSETTINGS=/screen in the most upvoted answer (and many others) will degrade your pdf's quality.

From the ghostscript manual:

-dPDFSETTINGS=configuration Presets the "distiller parameters" [...] Using any of these presets will involve altering the input, and as such may result in a PDF of poorer quality (compared to the input) than simply using the defaults. The 'best' quality (where best means closest to the original input) is obtained by not setting this parameter at all (or by using /default).

Also, useful options like -dNOPAUSE are implicitly specified by the -o option.

To convert any pdf to version 1.4 use

gs -q -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -o out.pdf in.pdf

The -q is only there to silence the command. You can leave it out if you want to see warnings (for instance for missing fonts) and so on.

Watch out: Ghostscript won't inform you about non-existent / non-supported versions, even without -q. For instance, if you specify -dCompatibilityLevel=1.9 (there is no pdf 1.9) you get a pdf 2.0 but ghostscript won't tell you. I couldn't find a full list of versions supported by -dCompatibilityLevel=. 1.0 seemed to be unsupported. 1.1 - 1.7 worked. 2.0 worked too, but created pdfs which did not conform to the standard (although they displayed just fine in evince).

You can check the written version using grep -oa '%PDF-...' out.pdf.
Also, I found that PDF/A can only be created by using -dPDFA. Sadly, all these options don't seem to be that well documented or documented at all.