It irritates me that advertisers often claim a product is "New and Improved". Surely, if something is new (ie, has not existed previously), it can't be improved! And vice versa!
There is no rule that says advertising language must adhere to perfect logic; however, in this case you are simply being too restrictive in your definition of new.
- coming or occurring afresh; further; additional: new gains.
- fresh or unused: to start a new sheet of paper.
- (of physical or moral qualities) different and better: The vacation made a new man of him.
- other than the former or the old: a new era; in the New world.
- being the later or latest of two or more things of the same kind: the new testament; a new edition of Shakespeare.
Among these definitions of new, there certainly seems to be a notion of something that is the next iteration, or a refurbished/remade product. So, "new and improved" could be argued to be redundant, but not an oxymoron (unless you intentionally ignore some meanings of new).
It's advertising-speak, and that means it doesn't have to mean anything literally. (When an ad announces that something is "Free!" does anyone think you don't have to pay money to get it? Dream on!) Basically, some kind of research has determined that using "New! Improved!" (and, especially, "Free!") in an ad headline, copy, or voice-over leads to some percentage of increase in sales. It's about creating an impression.
That said, something can be new without being improved. And something can be improved without being new. A thing can also be both new and improved: it can be argued that Windows 7, say, was, when it was released, both a new version of Windows and an improvement over the old version (Vista). It was still, for all intents and purposes, a new version of Windows and an improved version of Windows. Vista was a new version of Windows that many people felt was not an improvement over Windows XP. New, but not improved. Therefore, the claim "new and improved" is neither a tautology nor an oxymoron.
I wouldn't worry too much about how accurate or honest or grammatical or self-consistent advertising copy is or should be. Most people hold it to a much lower standard than most of the rest of English.
(Image comes from: http://xkcd.com/870/)
On the contrary, it is more like a tautology.
That means that both words state the same and therefore one is redundant.
While the two words do carry slightly different meanings, they both convey the same general idea:
new as compared to old. Here is the new one and there is the old one. ~Shows that this has replaced the older version.
improved and thus better than the old one. The old version was unreliable, this new version is much improved. ~Shows that it has been remodeled or somehow made better.
Therefore, we could take away either word and essentially have the same concept.
The better word to keep would be improved since 'new' can be incorporated in its meaning', while something being new doesn't incorporate 'improvement' (consider new versions of your favourite childhood cartoons/TV shows!)
Hope this helps.
N.B.: It might be important to note that the word improved can be used for repairing items (like a damaged bicycle), in which case the item in question would not be new.
However, in the context of this question that sense is not relevant, since your broken and then fixed bicycle would not likely be the subject of an advertising campaign to sell it back to you.
The most typical examples of oxymorons are phrases in which the meaning of an adjective contradicts the very nature of the noun with which it is associated.
A well know example is a "deafening silence" or its symmetric a "silent scream".
In the example you cite, we have two adjectives and they don't have opposite meanings.
You possibly meant a pleonasm - a commonly observed phenomenon in advertising slogans . Yet "New and Improved" would not qualify either since, as many have already pointed out, newer things are not necessarily marked improvements on older ones.
 Celtic (Gaelic) etymology. Hear, hear.
Literally, possibly, but I classify it almost as an idiomatic expression and, like (nearly) all idioms, mean something different than the literal meaning of their compotent terms.
It seems to me that calling something new does not make it so. Windows versions don't need to be considered new but just improved over the last one no matter the numbering. Windows was an improvement over DOS but certainly not a new version of DOS. New and improved is at best old and impoverished jargon of the advertising world, not proper English. A several-page scan of a Google search gives only marketing-related firms using this phrase in their own names.