Very interesting. I would definitely call them ASAP. Their "buy back guarantee" might offer you some options since it came up clean when you bought the car. This kind of thing really makes you question CarFax's reliability.
As a former 3rd gen WRX owner, I can tell you that you'll love the car, just be careful with mods, as the new Subarus are notorious for cracked ringlands, even bone stock. Actually, the stock tune has unofficially been the cause of failure on many of them. It kinda puts you unto a catch 22. Reflash to an aftermarket map that doesn't spike lean at partial throttle, but reflashing can void warranty. Or leave it stock to preserve warranty, and risk cracking ringlands. Check out www.3gwrx.com
for a great '08+ specific forum that is very active.