It sounds like the NMEA converter draws power through the same fuse as your Seatalk. You added a load on this fuse which brought it closer to the fuse's rating. If it is drawing 4.5A at 12V and your solenoid draws enough current to drop your voltage to 11.5V (due to resistance in wiring or corroded contacts) that might be enough to cause the current to increase and blow a fast blow fuse. Measure the drop in voltage at the furthest downstream point for both +12V and 12V return (neg) when you activate the solenoid. If you have a switch panel and a ground bus bar that is likely your common connection point furthest downstream.