Just here to agree with Tom and Bob. Dip tube would be my fist check, especially on a gas water heater. They are cheap, fairly easy to replace and come in standard size(only may have to cut a little length off the bottom to fit height of water heater, dip tube is usually about six inches off bottom of tank). On a gas water heater, a fualty thermostat means a bad gas valve, which is spendy and almost worth replacing water heater itself. You said water heater is fairly new, how new. It may be under warranty. Might be time to have the installer back to check this out. Good luck and please let us know what you find.