I was sure that the arXiv FAQ had an answer to this, but all it has is this, which tells you how to disable automatic hyperref. I don't do this, but it will certainly work if you simply create at 00README.XXX file, say nohypertex in it, and just roll your own hyperlinks (it won't ignore anything you write in the document; this will just disable its own attempts at hyperlinking). I remember I did this in the first version of my first paper.
In any case, my own papers seem to have no special provisions: I have \pdfoutput=1 at the top, and then \usepackage[colorlinks]{hyperref} later. I also have a \hypersetup changing some link colors, which is obeyed.
Do you put colorlinks in the \usepackage or the \hypersetup? Try doing the former. The hyperref manual suggests that some options have "restricted" use, so this may make a difference.
Finally, it's possible that the arXiv scripts are to blame here: perhaps they detect the loading of \hyperref and modify their own use of it accordingly.
Edit: Although you seem to have gotten some use from what I wrote, it does indeed look like the arXiv is ignoring the pdfborder = {0 0 0} directive. One workaround that I tested myself is to use the alternative command linkbordercolor = {1 1 1} (i.e. white), which is not ignored. I don't know what was going on with the other option, unfortunately. 00README.XXX is not required.
hyperrefwas the problem. – lockstep Oct 4 '11 at 5:29