Long time ago.... but what the hec,

Had same problem on one our 2008 R2 Servers

Setting Max Degree of Parallelism to 1 resolved it.

I am assuming it has something to do with the way the optimizer works with parallel queries (such as a union)