Estimated and even supposed actual cost suck for these types of estimates. The real problem is likely futher to the right in the execution plan. I can see that the first one has nested loops and that the second has a merge instead.

My recommendation would be to read the article at the second link in my signature line below and post the actual execution plans using the methods from that article.

It may actually turn out to be the insert into the temp table that cause the problem if you're running on a new SAN. It seems there's been a rash of "lemons" hit the streets from a couple of previously trusted vendors, lately. I don't want to mention the name because I don't want to get sued for saying their products have really taken a turn for the worse.