Hmm I've heard of issues like yours.
I would do a MD5 checksum on the kernel you downloaded. Its a 5MB file this means a small error in downloading can cause a big error in installation and functionality.

The other point is to make sure you have the right file type.
Recovery files are in .zip format not .tar which is for adb/Odin installation.

Try downloading it again. And before installation wipe cache, dalvik, factory. After installation do “fix permissions “.

Let me know how it goes.
Oh and a handy tip, I recommend not making nandroid backups of custom firmware. I know its practical but u could mix it up with ai nandroid from your stock build. And doing the wipes, installing the from and then the kernel is, for some reason I don't know, much quicker than doing a nandroid restore.