I've just had this same problem myself.. i have units that are created by player 12 (brown, i believe) that march out. But, when i kill them with my hero, they don't give gold. I've done everything mentioned in the above posts.
BUT i can't find the "Player - Turn Gives bounty On for Player 2 (Blue)" (or whatever colour) action. It doesn't appear even in the search option.
Where the heck is it?