I tried a different Sprint Store yesterday. After about 10 minutes the tech came out and told me they couldn't fix it so they would just give me a new one. Another 10 minutes and I was out the door, brand new Evo in hand. It was like I was dealing with a whole different company!
So for those with this problem, keep trying! There is hope!