Don't worry about it too much

Until you conspire with the first PC to backstab the party, they will stick together simply because they're the players. It's not perfect storywise, but it's often better than finding some elaborate explanation that breaks the flow of the game.

A larger evil

Have an enemy ready that catches them together at one point in the story. For this evil NPC (works best if he's a higher up, cult priest or sergeant or something), it's clear that the party conspires against him, that they are together. Fighting against him or just foiling his plans will make the party move closer together naturally.

I do several things to keep the player characters interested and invested in each other.

1. At the start of the game, I insist that players coordinate backgrounds (subject to my approval) such that each character know at least one, and preferably two or more, of the other characters. In general, I prefer these connections be positive; the most negative I will usually tolerate is on the order of a friendly rivalry. In general, I also prefer that if you start from any one character, you can get to any other character by following these pre-arranged links. (In graph theory language, the players are all connected, although indirect connections are fine; the alternative would be two more more sub-groups connected internally but not to each other.) And finally, I try to ensure that each connection is more than trivial, but not necessarily life-binding.

So for instance, "We met in a bar twenty years ago and never saw each other again," is trivial. "We are cousins who are best friends and we are rarely separated," is life-binding and more than I look for (although it's fine if that's what they want.) Things like the following are what I look for, and/or what I've seen in the past:

• Our characters served in the same unit years ago, and knew each other, but haven't kept in contact...
• I served as a mercenary escort once, while he was travelling with his master from here to there; along the way, this happened....
• We weathered the siege/plague/earthquake of wherever together some time back....

Now, some players are genuinely not wired that way-- if you ask them for backstory, they freeze; if you given the one, they can't connect to it. When I run into a player like that, I have to respect that, but I try very hard to get everyone to adhere to the guidelines.

That does not directly solve the problem. (It actually solves the problem of getting the characters all on the same page at the start of the game.) But it does often give me enough to work with to do the following:

2. With enough insight into character backgrounds, and with overlapping backgrounds, I try to give every character an mid-term to long-term goal or plot arc, and then I try to modulate that by giving at least one other character a minor to moderate interest in how the first character's arc plays out.

It's important (to me, for the games I want to run) that these arcs not be strictly opposing: If one character has sworn blood-vengeance on an NPC, I won't give another character the goal of keeping that NPC alive. But I might give another character the goal of getting something from that NPC before his death, or getting the NPC to do something, etc.

3. And I also try to modulate this in another direction by giving other characters-- ideally, not the same one-- influence over the plot lines. So continuing that thought:

   • Player A has sworn to kill Sir Odious, his parents' killer
   • Sir Odious has information that will help Player B in her quest to do something else
   • Player C knows someone who can be bribed into giving up information about where Sir Odious will be

In that way, for each of the various player sub-quests going on, at least one or two others will be involved somehow, even if only at the periphery. Ideally, Player B has some motivation for something to happen, and Player C has something he needs-- something at least moderately costly or risky. They are invested.

One thing I would not do-- at least not again-- is what you tried:

I've had players create characters (with backgrounds) completely secretly from each other with the hopes of allowing the character interaction to be heavily role-played at the table. Didn't work because of very incompatible characters.

I've never done that, specifically, but I've inadvertently done similar things and it never worked well. It seems like it should work, especially if you pattern it similar to what I've outlined above, but there's a structural weakness to it: If the players, starting out with the relative blindness of only knowing their little part of the background, they just might not see those connections you built in for them, and won't give themselves the incentive to start sharing information. And if your players were the sort that would do that naturally, you wouldn't have to go through these acrobatics in the first place.