I got this issue in one of the last updates i did.
I'm installing both packages from melpa.
I temporarily solved the issue using an advice, as magit-key-mode has no magit-key-mode-hook - I don't know if this is related at all.
By the way, great job with evil in general, it's working great apart from this small issue!
Cheers,
Alessandro Piras