Chiming in to echo my results:
"New" tags are less than reliable. They come and go with seemingly no rhyme or reason.
All my truly new (never before aired) shows (whether viewing info as it airs, info in my shows, or info in the guide, future or past) are showing they first aired the previous day when they obviously did not.
None of my recordings seem to have been effected by this strange bug.