I assume that you also have a big enough gas meter since the gas company was of no help. The meter should be large enough to handle the heater plus any other gas appliance that may be used as the same time.

Although I am not completely sure, I would expect that all 400k BTU heaters to require the same the gas pressure since the flow rates are the same. One alternative is to go with a lower BTU rating which would require less pressure. It just means longer warm up times.