I am also having the same problem on the Samsung Charge. I have to restart my phone to sync, and it only works once. I have to restart my phone everytime to get email. If I remove and re-add the account, it works for a few hours and then fails.
I recall this problem happened in the spring, and resolved itself. I am thinking its not our phone settings since it resolved itself before.