As Tom points out, you are behind with versions, and you should install CU10, which is the most recent Cumulative Update. I would not really expect this to address the issue, since performance fixes are typically hidden by trace flag 4199.
There are two slow versions of the SELECT COUNT(*) query, but there is no fast plan to compare them to. And as I pointed out last time, the query is about unreadable, since there are no line breaks in it. I did notice one thing, though, when I scrolled through it, though: there is an OR condition. The optimizer rarely does a good job with OR, and rewriting with UNION often pays off.
As for the other query, I notice that this is unparameterised SQL which is bad in itself. It means that for every new set of parameter values there will be new compilation and a new cache entry, so this is a resource waster. In theory, though, you should get the best plan for the parameters you have, but apparently that does not always happen.
In any case, I would first clean up this query by parameterising it. This can certainly lead to parameter sniffing issues.
It also seems to me that this query is bigger than the query text seems to suggest. That is, the plan have more operators than I would expect, and I see table names not appearing in the query. Am I right to assume there there are one or more views in the query?