Do you have Advanced Auto Task Killer installed? If so, remove it. It worked for me.
A power cycling phone sure can get old really fast so please know I'm ready to find the perfect solution to keep it on until you say otherwise. At this point, I'm very glad to know that you've gone through with some troubleshooting including a master reset but I've got an idea for something else we can try that should help.
Have you tried putting your phone into safe mode http://vz.to/ruJiUa ? This will allow us to isolate the issue to either the device itself or potentially an application. Please try this tactic and let us know how it responds. If all goes well while in safe mode, there may be an app that we'll want to get rid of.
Follow us on Twitter @VZWSupport
How many apps did you put on after the factory rest? Hint, that's the problem.