I changed what you said to change, and no Nei.
I see from your screenshot that you had success, though. I am very new at this, and the possibility that I screwed something up is fairly high. I went to offset CA58 and put in 4E 71 4E 71 4E 71. It did not work. Did I do it correctly? The Game Genie code in this thread did not work, either.
EDIT: The Game Genie code DID work, once I switched from Kega Fusion to Gens. The way to get it to work is to wait until AFTER you have chosen your party (if you want, say, Rolf, Nei, Rudo, and Kain, you have to choose Rolf, someone else, Rudo, and Kain, because that someone else will be replaced from Nei in your party). When Rolf says "Let's get going!", turn the code on, and Nei will be in your party. However, you have to do this every time you change your party. I'd much rather just hack the ROM, though, than go through this process each time. It's the same as hacking the save state to insert Nei.