If both hot and cold were softened before the WH was replaced then the softener is installed correctly so we can rule that out.

Replacing a WH should only require disconnecting the cold water in line and the hot water water out line, the T&P drain line, and gas line or electric. Nothing else should have been touched.

It is not unheard of for someone to reverse the hot and cold at the WH and create a problem that wasn't there before.

Who installed the WH?

This would be backward from recommended. Generally, if you leave one unsoftened, it would be the cold as hard and the hot as soft...(so as not to mess with your drinking water).

did the lines get reversed somehow?

Also, hot water dissolves things more easily than cold. What could be in your lines or other systems that could be dissolving that mineral?

OR, what is growing in your hot water tank (what is its temp) that is releasing sulfur compounds?