Apparently the source of the problem is that TikZ behaves differently when the TeX file
is compiled with pdftex/pdflatex instead of the standard tex/latex.
Instead of simply embedding PostScript into the DVI file, as any sane system would do,
it apparently tries to draw figures using characters from some special fonts.
In my opinion, TikZ authors should be crucified for this.
Mathematical papers are supposed to last a little longer than 10 or 15 years.
In 10 or 15 years PDF will be replaced by yet another format,
and all TeX files that are tailored specifically for PDF will become unusable.
So long for durability.
For this reason I urge everybody to ignore Andrew Stacey's advice (no offense meant).
One more reason to use METAPOST instead of TikZ. They seem to have
similar functionality, but METAPOST is much more powerful when it comes to solving
systems of equations, has more convenient syntax (no annoying backslashes),
and is also an order of magnitude more portable (for example, any document with METAPOST pictures looks
exactly the same in DVI, PostScript, and PDF formats).
As for the fonts, we should blame arXiv for this.
The DVI format is device independent.
However, a DVI file must always be accompanied by all fonts that it uses,
except for the standard Computer Modern family.
The arXiv simply gives you the DVI file without any fonts, which I find ridiculous.
Since the paper under discussion uses some weird PostScript fonts,
and the arXiv gives you a DVI file without any fonts,
it is natural that the DVI file is unreadable on many machines.
I apologize for somewhat strong language, but I feel very strongly when
it comes to the issues of portability and/or durability of mathematical papers.
For example, 10 or 15 year old LaTeX files are often no longer compilable on modern TeX systems
and require some voodoo magic on my part, because of the changes in the LaTeX
and its various packages.
For this reason I switched to Plain TeX about 10 years ago.
A Plain TeX file created in 1982 will compile without any errors and will produce
exactly the same document in 2012 or in 2042.
[If I am allowed to comment on the appearance of the paper, I must say
that it looks quite weird with the current fonts. Apparently, PostScript
fonts are used to typeset the main text, but all formulas are still typeset in Computer Modern.
Since the two fonts are obviously incompatible in style (for example, they have
different thickness), the end result is horrible. If I were to read this paper,
I would recompile it using the standard Computer Modern fonts.
Again, no offense meant.]