I won't say it is the task killer 100%, it could be another app on the phone causing a conflict. However, task killers have to be set up properly and you have to know what you are killing when you are using them. They are also not really necessary when you first get the phone. They may become needed, by some, when they have problem apps installed.
I would look at the most recent apps you have installed. If you have one that you installed in the last day or so, it may be the problem. Try removing it and restarting. If the problem continues, try removing the task killer and restarting. Lather, rinse & repeat.
As for the Verizon people.....where do you think many of them get their info? Most of them are picking things up word of mouth or from here. Either way, I am willing to bet that the guy/girl telling you what to put on your phone does not own one.