I had this exact error after running a package upgrade, which included evil.
I believe the root cause however was that I had an old reference to a manually installed evil folder in my init.el loadpath.
I removed that, quit & restarted emacs, and the problem had resolved itself. If you don't have the same init.el problem, perhaps just try removing and reinstalling evil.