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.]
Best Answer
My comments above formulated as an answer:
People typically post a preprint on the arxiv at the same time that they post it on their own homepage, with the goal of disseminating their work to their colleagues. (These days, posting on the web is more important than journal publication for sharing your work, and the arxiv is the central repository for math on the web.) This is often at the same time that they submit to a journal, although sometimes they wait for feedback (as Joe Silverman suggests in comments above), and sometimes they spend more time polishing their preprint before submitting it (as Darij Grinberg suggests, again in the comments above).
The conclusion seems to be that it is standard to post on the arxiv as soon as one is ready to share one's work with colleagues, and that this is often at, or close to, the same time that one is ready to submit one's paper. In particular, it is quite common to post on the arxiv at the same time as submitting, or not long prior to submitting. (But there is nothing wrong with posting on the arxiv and then spending some more time polishing your preprint before submitting it to a journal.)