Why does it take so long to calculate an Execution Plan?
I hate to answer my own question, especially since I have had so much help from others to work out the solution, but here goes.

The problem was due to some dud statistics in the database. Looking at the execution plan, the optimiser was expecting 11.5tb of data returned from the query. In reality is was receiving 87kb. I now know that huge mismatches between expected and actual rows returned is a sign that the statistics are out of date.

Simply running

exec sp_updatestats


forces the database to update the statistics for all tables.

This has taken the query execution time down from 3 minutes to 6 seconds. Everyones a winner!

Thanks for all the help guys. :0)