What I've got is a purely resistive three phase load protected by fast acting fuses. The total load is 250kW, but each leg is only seeing 310A maximum. I typically rate my fuses 125% high to avoid nuisance trips, which is why I'm using a 400A fuse.

This cabinet is getting hotter than usual, though, at about 80°C (176°F). I believe this is the root cause of my trips. Adding fans to cool the cabinet is a cost prohibitive fix. I plan to replace the 400A fuse with a 450A fuse, but I want to make sure that I'm still "safe" if I do that.

Is there a rule of thumb guide for sizing fuses in higher ambient temperatures?

 

depending on the load type, try using slow blow or normal blow fuses instead of fast acting of fast blow. or posibly a circuit braker.
motors, incandesent bulbs, transformers take an initial current draw a fair amount grater than their rated amperage.
the heat in the box could be a contributing factor also because fuses are heat activated. you should be able to go biiger but consider the wire size your useing. since thea main point af circuit protection is to protect the wireing it is hooked to.
(if you need more info check out the informational vidios and articles in the rest of this site.)

 

You have found the real problem and it is the pre-heating of the fuses. I would make every effort to fix the real problem, the heat, before oversizing the fuses and thus neeeding to change the wires to better quality. Compare the price of improving the wire to the cost of allowing ventilation.

You might be amazed at how little air is required to cool an enclosure.
BTU = 1.08 CFM Dt
BTU = 3.413 x watts

I can't imagine a lot of watts being generated by a set of fuses. It might require only 10 or 20 cubic feet of air per minute to make this work properly.