DPDT >30 Amp Latching relay
I currently use a DPDT 30 Amp relay to switch between a utility
  supplied 120 VAC and an inverter supplied 120 VAC.


And...


  Does anyone have a solution?


It's a double throw relay (DPDT) so energize the coil from the incoming AC (from the mains) and rewire the relay contacts accordingly so that when the relay is inactivated (no AC power), the inverter output is connected to the load.