Strangely enough not long after I sent that to you, I popped that in the new PC port. Let me know if it works please because 1 other person had the same trouble, I gave out the same advice, obviously, and it would be good to confirm whether it might be some larger issue or just the issue I suspect it is (needing to bump into an unmarked dude on the radar). By the way, when Majima is active, there is no 1 set place on the map for him to be active. When you travel from area to area, he will travel with you, so if you go away from that mission marker to another area where he spawns for the Let's Fight trophy, like in front of the walk-in grill restaurant (forget the name) I think near the SE of the Millennial Tower, there'd be a random dude to bump into near there, too. He'll move, but the TYPE of Majima he is should stay the same (Zombie, Slugger, Cop, etc.).