I fixed my issue in a strange way.
I just about went insane trying to set up my two Gmail accounts on the Samsung email app after Verizon Message+ somehow screwed the accounts up. I kept getting error messages saying "unable to connect to email server to verify your account information. no response from server." I did three factory resets, cleared all of my Google backup data on both accounts, and emptied out my Verizon backup files online. Nothing worked. Obviously this was a major pain, as I had to reinstall all of my apps and re-do all of my settings.
Almost by accident, I tried verifying my Gmail account info in the Samsung email app while I was using 4G instead of being connected to my home wireless network. It suddenly worked.
I have no idea why being on my network was keeping me from setting up my Gmail accounts. I was having no issues whatsoever with my home network: all other apps and my laptop were connecteing to the internet just fine. I had spent hours searching the web for solutions, none of which worked. It was insanely frustrating.