New (and) Improved ... how can you have the one with the other?

It's either 'new' and therefore wasn't around previously to be improved upon.
Or it's 'improved' based upon an older version and therefore can't be 'new'

Options:

• New
• Improved
• Newly improved