The first thing you need to do is get your water tested. In some states, your county extension office or land-grant university will do some basic tests at low cost, but at the least they should be able to point you to a reputable testing firm. Without a good test, we're shooting in the dark. Also, how much water do you use -- how many people, bathrooms, Roman tubs, etc.?
One shot that is likely to be on target, however, is that you've got an iron-related bacterial problem in the water heater. Google "hot water smells anode" and do some reading. One on-line site offers a good description of the problem at http://www.cleanwaterstore.com/techn...ater-odors.php and a bunch of related reference information listed in the "Technical Resources" list on the left. They also do basic water testing via mail-order: http://www.cleanwaterstore.com/well-...test-kits.html.
I had the problems you described and ultimately solved them with a chlorinator and carbon filter in-line before the softener and a new anode rod in the water heater. All that doesn't come cheap -- around $1500 for a smallish chlorinator, carbon system, and softener rebed; the price goes up as the size goes up. (That assumes you do it yourself -- not hard if you're handy.)