I take it that the SQL server is a 64bit box and doesnt have any throttling going on in terms of Max Degree of Parallelism, max memory usage.
How many processors does the box have?
Also that the Temp Db, source DB and logs are located on different physical disks rather than being on the same disk.
I personally cant see anything wrong with the query and if it works ok on other boxes, then it really can only be hardware configuration that is a problem.
Out of curiosity have you tried running the query with the Option(MAXDOP 1) to see if that helps, as i noticed a lot of parallelism going on in the plans and sometimes it can impact the query signficantly.
Yes it's 64bit, has 32gb of memory (although only 20gb allocated to this instance) and the MAXDOP is set to 0/unlimited (same setting as the old server). The box has 2 virtual CPUs, which is the same as a different SQL 2005 box it ran fine on, so I don't think there is an issue there.
The only reason why I don't think it can be hardware related is because of how the query runs fine on SQL 2005 servers but not on any of our SQL 2008 R2 servers. This is true of both virtual and physical servers with varying amounts of resources, so it must be something to do with 2008 R2 I think....struggling to think what though!