Well, if I'm not mistaken the Game Genie would convert 72-pin NES games to a 72-pin NES. You'd need an adaptor that converts 72-pin NES games to a 60-pin AV Famicom.

Don't use the Game Genie. Just connect the game to the AV Famicom using the adaptor. That should work. If not, try different games to see if it's just the game or the adaptor. If it's the adaptor, you'll need a new one. They're hard to find anywhere but on eBay.