With the Zeners across the Gate-Source junction, I think that we can eliminate the gate as the problem. You did say that the FETs were overheating, so I would expect that you are turning on one leg before turning off the other. One characteristic of this problem would be the H bridge functioning properly at full speed in either direction and overheat at any intermediate speed.
Try this: Work on one side at a time, one P and one N FET. Instead of wiring the two drains togather, use a resistor to limit current. With 100 Volt supply, I'd start with a 10Kohm. Watch the voltage across the resistor with an O-scope and look for spikes at the transistion. If you get spikes, then work on your gate drive circuit to do the "turn-off" faster or "turn-on" slower.
I assume that you not using one of the gate-driver chips and that you are using one pin off of a PIC to control both the P and N FETs on one half of the bridge.