I just spent 45 minutes on the phone with Sprint. Apparently they are getting a lot of calls with people complaining about data speeds on the 4G LTE.
The Sprint rep tried a bunch of things, but even though I'm showing three bars of signal, I have no Internet. It does work sometimes, just not at my phone or office!
She suggested taking it back to a Sprint store and having them reactivate my OG Evo until this phone gets fixed, either with some kind of software fix, or a new hardware version. She says they are logging all these issues, so they can figure out how to fix it.