I don't see any problem with the file you linked to. The logo with the 'Themrad' string renders just fine with the latest version of Ghostscript (9.02).
But then, the PDF file may be a new version also ... its metadata say it was created on March 18, 2011 (but your question is from August 16, 2010).
This version of the PDF has embedded all the fonts used (different faces of HelveticaNeue).
Font embedding may not have been employed with a previous version of the file, which would explain some rendering problems because Ghostscript would have needed to substitute the original (unembedded) font in order to be able to render the file at all...