Did you put fresh batteries in the new thermostat

I would take off the thermostat and check a few things.
1. Measure 24V AC, make sure the voltage is within reasonable range.
2. Use a jumper to short G-R terminals to test the fan. Probably will also try Y-R for cooling and W-R. You can find the definition of terminals below. Also consult the manual of your thermostat, and the labels on the terminals.
http://wiki.xtronics.com/index.php/Thermostat_signals_and_wiring