Your description makes me question whether the new TV has been set to 'air' or 'antenna' mode in the setup menu. Most TVs default to 'cable' mode. Some now have an 'auto' setting, but if 'air' or 'antenna' is an option, use it instead of auto.
Please consider posting a link to your TV Fool report. We will be able to offer advise about antennas once we know what signal conditions are like at your location.
http://forum.tvfool.com/showthread.php?t=4