From what you describe, I assume the game you're running is a "serious" drama/sim type game, where people don't like doing something just for metagame reasons. "Well, we know he's a new PC, so we should just accept him as a brother." Some people run games like that, that's fine, but I don't prefer that style and it sounds like that's not your game style either, so let's talk how to make it work within a "game fiction first" framework. In that framework, there is never any "force them" to do anything, so you're right to not have done so.
You have two ways to rectify the problem - in game and careful metagame.
In game, you can generate opportunities for these people to meet in a way that they would then naturally ally with each other. I don't know what your campaign is about, but maybe they are threatened by the same force, or have some common cause. But make it all believable within the game. The party/new PCs are both balking because they can't figure out a way to join up that, when viewed from the characters' perspective or from an outside story perspective, makes sense.
With careful metagaming, you need to help the guy craft his new character's background to align well with the party. You can also consider talking frankly outside the game as to what the missing components of trust are, and then using that to feed into your in game approach above. It's fine to run full sim in game, but everyone (player and GM) has to understand that they need to construct their characters/plots/etc. to bring everyone together.
We had a problem like this in a serious game I was in. We were all undercover wizard killers, facing a widespread demonic conspiracy, and we had to maintain strict secrecy. So we get this new gnome character in who is just acting like a total insane spaz all the time. Like to the point that he wouldn't/couldn't answer a normal question. We kept him outside the secret for a little while, just interacting with him via our cover identities, hoping that maybe the crazy thing was just an act and we could find an angle where anyone could take a chance on trusting him. We were feeling the metagame pressure to try to include him somehow, but couldn't find a way to justify it in game. Eventually he happened into our secret when we got attacked. Afterwards we had to have a serious talk with him about our mission, and he would just respond "Wheee, turnips!" We explained very carefully to him that he had two choices - make enough sense that we felt we could trust him and join up, or we would sew him into a weighted sack and throw him into the river, because those were the only options that would allow us to survive. He shaped up. If he hadn't, I trust his next character would have aligned better with the campaign and our group.
For people who are trying to play an immersive game, "forcing them" to take a character basically destroys the value of the game for them. There need to be in game reasons. Now, they shouldn't be complete drama queens about it - "we kinda like him and he seems reliable and he has skills that could help us" is more than enough reason, if they are looking for more then they are being a bit unreasonable. Though heck, you can come through with a vision from someone's deity or something about "his destiny lies with you..." From the player's end, he needs a reason to throw in with them too, and no massive dealbreakers regarding the ability to trust them. This does require some coordinated design on your part (and the characters' part) up front.
If the party dynamic means that they would never trust anyone new they found, or that they would never be trusted by anyone, then that's a bad initial party dynamic - same thing with a new PC. "We are all distrustful loners" won't work well for that, unless you have an in game construct to force it (they all work for the government and are given orders; they are all captured and put on the same slave barge, etc.). And if it comes down to it, as GM you (probably, assuming a trad game) control the weather and NPCs and gods and whatever, you can force them into a potentially bonding situation together if you really have to.
Heck, here's another example. We had a guy join one game of ours. We were a Serenity type group of independent spacers in port. He showed up for a job interview. (We knew there were new PCs to take on, and we could always use more help, so we accommodated the metagame need for new character intake by putting up a job posting.) This guy shows up, and he won't answer any question we have. What do you do? "Things." What skills do you have? "Good ones." What value can you add to our crew? "I take care of problems." What kind of problems? "Big ones." We ended up dis-inviting that player to our game, as his play style was just a poor match for ours. He wasn't a new player to our group either, but his similarly disruptive shenanigans in the past had really diminished the enjoyment of our campaigns for everyone else involved. This was the last straw.
Some groups just get together to hang out, and don't really sweat the logical details of the game fiction. In that case, they'd just welcome him in and set off to kill some orcs. But some games are allergic to "silly" happenings, and in that case you have to find a way via design and the other "knobs" of game fiction to get them together.