Why would SET ARITHABORT ON dramatically speed up a query?
A little dated, but for anyone ending up here with a similar problem...

I had the same problem. For me it turned out to be parameter sniffing, which at first I didn't understand enough to care about. I added a 'set arithabort on' which fixed the problem but then it came back. Then I read:

http://www.sommarskog.se/query-plan-mysteries.html

It cleared -everything- up. Because I was using Linq to SQL and had limited options to fix the issue, I ended up using a query plan guide (see end of link) to force the query plan I wanted.