Multi-party negotiations would be great!
If this can't be done with an easy-to-use interface, here's a less-than-perfect idea using a interface similar to the Civ 3 one-on-one screen: Among the things you could ask for or offer would be "Peace with the Carthaginians" and "Peace with the Romans" and so on. Since the computer keeps track of what all the AI civs are willing to give and receive, it would know right away what Rome would need to offer Carthage to get a Peace Treaty, so if you asked Rome for "Peace with Carthage" Rome could tell you right away what it wanted in exchange from you. That, of course, wouldn't necessarily be exactly equal in value to what it needed to give up to Carthage, it would depend on Rome's attitude towards you, Rome and Carthage's attitudes towards each other, which of them was winning their war, their relative power to each other and to you, and so on, you get the idea. And it wouldn't matter which civ you talked to, either. Say Rome was beating up on Carthage, and would be willing to stop for 50 GPT, but the war dragged on because Carthage wasn't making that much. If you wanted the war to end for your own reasons, you could approach Rome and ask for "Peace With Carthage", they would ask you for 50 GPT, essentially thinking to themselves "If Carthage can't give it to us, maybe you will." If on the other hand, you talked to Carthage, they'd think "we'll need 50 GPT in order to get the Romans to give us peace" so they'd ask you for 50 GPT in exchange for "Peace With Rome." No matter who you negotiated with, the result would be the same, you pay 50 GPT, the Romans get 50 GPT, and they stop beating up Carthage.
It would work a little different if someone wanted you to stop a war you were in, but once again, it would take advantage of the computers ability to conduct instant negotiations between different AI civs while you're still in the diplomacy screen talking to one of them. If Carthage wanted you to end your war against Rome, they would ask you to do so. If the war was going well for you, you'd ask Carthage for something in exchange, which they might agree to if peace between you and Rome would benefit them. Or, they could come to you when Rome is kicking your butt and ask you for "Peace With Rome" and "spices" knowing that the Romans won't stop attacking for spices since they have their own, but will stop for iron, which you lack but Carthage has plenty of. Carthage gives you nothing, you give them "Peace with Rome" and "Spices", and instantly you have a peace treaty with Rome, without ever talking to them. If Carthage wants you and Rome to stop fighting badly enough, they might just go straight to Rome and offer them iron in exchange for "Peace with (you)", but since that would be AI-to-AI, you wouldn't see the negotiations, all you would see was Rome offering you a generous Peace Treaty, perhaps with some text like "Carthage has asked us to spare your puny civilization for now" so you'd know who was offering the Romans something. If you turned down the Treaty, the deal between Carthage and Rome simply wouldn't occur.
Unless of course, Carthage was really desperate for you and Rome to make peace for some reason. It might be strange, but maybe Rome would be seriously kicking your butt and then suddenly want to talk, saying "Carthage has asked us to spare you..." and offering Peace Treaty and 20 GPT. You'd know that Carthage must be offering them quite a bit, probably significantly more than 20 GPT, in order for them to stop kicking your but and give you money. And if you asked Rome for more, the computer would instantly check to see if Carthage was willing to give Rome that much more, and if they weren't, Rome wouldn't make the deal with you.
The point of all this is that, at least for simple Peace Treaties, you could have some semblence of multi-party negotiations without actually having a multi-party screen, just by taking advantage of the computer's instant knowledge of what each AI civ has and is willing to give and receive from each other.
Of course, it'll be cooler to have real multi-party negotiations. I'm just putting out these thoughts as a backup option, so that the designers don't give up entirely if the multi-party interface gets too ugly and confusing.