Hot water heater and gas-stove not working at the same time
Usually the gas pressure regulator is near where the gas line first enters the house. After the regulator is where the gas line will split off to go to your appliance.
When the gas company person said the regulator was bad they were referring to this common regulator. It's going bad is why it affected both of your appliances.