For the sake of anyone who has this same problem in the future, I confirmed that this is a bad sensor. I found this thread because i had the exact same problem.
Luckily I ordered 2 of the ultrasonic sensors, after trying everything I could think of, I opened and plugged in the second HC-SR04. It works perfectly... same code, same pins. If you have this problem, my suggestion is that you get a new ultrasonic sensor.