well, this gets a bit complex, but basically the insect came first, and then the carob-tree became known as the locust-tree due to the resemblance of the carob pod to the bug; and finally the New-World trees so called may possibly have received their name from the resemblance of their fruit either to the carob-pod or the insect itself.

in the first case, this OED note is of some interest:
[The Gr. name properly denoting the insect, is applied in the Levant to the carob-pod, from some resemblance in form; and from very early times it has been believed by many that the ‘locusts’ eaten by John the Baptist were these pods. The application to the cassia-pod is due to confusion with the carob-pod.]

also, not too long ago (cf. Civil War draft riots) the clubs carried by NYC cops were called locust-clubs, from the wood used.