My husband and I are having the same problem!! We've both tried everything you described.
We are both using Android Incredible 2's, all systems updated, via Verizon. The problem is showing up in our phones, tablet and home computer. I agree- it sounds like a server issue.
We are both getting very frustrated with it!