In a brainstorm earlier, I thought that 3-4 Abyssal Gatekeepers might help with that, perhaps in the Darksteel Brute slots. 
Negator : barring a flying weenie horde, I've found that Abyssals are an outstanding method of keeping your opponents off you in the early stages of chaos / multiplayer games involving a lot of aggro.  Nobody wants to lose their quick starts, so they generally leave you alone.  The danger then comes from the other player/s with board disadvantage, who will do anything possible to get rid of your Gatekeeper, clearing the board and saving their own butt...but by then it's done its job, and you're well on your way to establishing the kind of tempo you want.
     I play almost exclusively chaos / multiplayer during breaks at one of my jobs, and the games usually consist of three or four players (we play Allies / 5-Star if we have five players), so the environment sounds pretty similar to yours.
Some card explanations: 
9 Board Sweepers, 0 Spot Removal 
This is a multiplayer deck. I haven't seen an example of a creature which spot removal can deal with which the mass removal listed cannot. Also, with the amount of mana this deck can produce, the argument that spot removal is less costly mana-wise has little merit. 
     Anything with regen can avoid the Oblivion Stones and Deeds.  While the deck may produce a ton of mana, I'd definitely rip the O-Stones out of the build for something along the lines of Edicts (whether Chainer's for the flashback, since you have the mana, or Diabolic for the instant speed) or additional creatures (see below).  Gotta love Mutilate, though...
The only true difficulties with this deck that I have experienced are with combo decks, mostly Pandeburst. Outside of multiple early Duresses, this deck has little hope against combo. Does anyone have suggestions on this matter? 
     Pernicious Deed is golden, obviously...  How about Plague Bearer?  No synergy with the board removal, but he can dust zeroCC critters without breaking a sweat, plus lay waste to tribal decks and possibly keep you from taking those early beats...  Doesn't help much against Pandemonium, but...
     I hesitate to suggest graveyard hate in chaos unless your deck depends on empty graveyards, which, in this case, doesn't apply.
     As for your problems with combo in general...that's always a problem in multiplayer.  Generally speaking, once the rest of the group realizes what deck the combo player is piloting, he's the target.  Is this not so in your group?