I played this the first time and he got away. I tried to do it again but the assassination marker was gone and I had the message to kill my target for the rest of the game with no way of finding this guy again.
I bit the bullet and started over through a new save just so I could get back to that mission and I was finally able to kill the guy. Here is what I did:
When you go to the location and spot the target's ship, DO NOT TRY TO PLUNDER IT. It is a waste of time. JUST FOLLOW THE SHIP TO THE PORT.
When Juan Garcia leaves his ship to get on land, leave your ship too and chase him on land so you can kill him.
This is a suggestion. It worked for me and hopefully it works for everybody else.