Serial Plan in plan cache
At first glance, this sounds like a classic parameter sniffing problem.

SQL Server builds an execution plan for the first set of parameters that get called when the plan needs to be compiled, and then reuses that plan over and over through the day. You can see what parameters they are - when you're viewing the serial plan, right-click on the select statement, and go into properties. On the properties window, look for Parameters, and then Compiled Values. That'll show you which values produce the serial plan.

To force the plan to always run parallel, you have several different options (many of which Erland covers in his excellent post that I linked to above), including:


Tune the indexes so everything gets a better plan (to get advice on that, post the plan &amp; server details as described in Getting Help with a Slow Query)
Temporarily, use a plan guide to pin the parallel plan in cache (but just know that if the query changes by a single letter, the plan guide will silently fail since it no longer matches the query)
Use an OPTIMIZE FOR hint in the plan to guide it towards values that produce a parallel plan
Use the new ENABLE_PARALLEL_PLAN_PREFERENCE hint in SQL Server 2016


That's just a quick answer - but for much, much more, read Erland's excellent post, Slow in the App, Fast in SSMS that explains how one query can get different plans, and how to fix it.