Did you check for blocking? Did you check what wait type the query is getting? Did you check for any messages in the error log?

It probably isn't a stats issue if the query plan can't be generated, but that doesn't mean it's a bug unless you've rules out every single other possibility (and there are lots)