Are those products on your home page?
Which version of Magento are you using?
You aren't missing anything. It seems you're doing the things in the right way.
But also that feature has been working fine.
Maybe you should reindex? The only problem could be cache but you said you've flushed.
I can't imagine (right now) another idea.
How are you showing the list? I mean, are you using a block or the out-of-the-box widget?
Is it possible for you to change the New products block by the widget?