The short answer is that there is a variety of ways of saying "orange cars," and that both coches naranjas and coches naranja are among them.
In traditionally correct usage, naranja or rosa as an adjective of color should remain unchanged, even when modifying a plural noun. However, Spanish (like all living languages) is changing, and in some areas, especially in Latin America, a construction such as los coches rosas would be perfectly acceptable and even preferable. You are right in stating the rule: Invariable adjectives (usually a noun being used as an adjective) don't change form regardless of whether they're describing something that is singular or plural. There aren't many such adjectives, the most common being macho (male) and hembra (female), so it is possible to talk about, for example, las jirafas macho, the male giraffes, and las jirafas hembra, the female giraffes.
Generally, the invariable adjectives are that way because they are thought of as nouns (as are la hembra and el macho), and they include the colors that come from names of things; esmeralda (emerald), mostaza (mustard), naranja (orange), paja (straw), rosa (rose) and turquesa (turquoise) are among them. In fact, as in English, almost anything can become a color if it makes sense to do so. So café (coffee) and chocolate can be colors, as can oro (gold) and cereza (cherry). In some areas, even the expression color de hormiga (ant-colored) can be used as a way to say something is ugly.
There are a variety of ways these nouns can be used as colors. Probably the most common, as you said, is along the lines of la bicicleta color cereza for "the cherry-colored bicycle." That's short for la bicicleta de color de cereza. Saying la bicicleta cereza is a way of shortening it even more. So the logic of saying las bicicletas cereza for "the cherry-colored bicycles" is that we're using a shortened form of las bicicletas de color de cereza. Or at least that might be an easier way to think about it than thinking about cereza as an invariable adjective.
So to use your example, los coches naranja would be entirely proper, although some variation of los coches (de) color (de) naranja might be more common in actual usage, again depending on the area.
What can happen over time, however, is that a noun used in this way can come to be thought of as an adjective, and once it's thought of as an adjective it probably will change form for plurals (and possibly gender). In Latin America, especially, some of these words (particularly naranja, rosa and violeta) are treated as typical adjectives that change in number. So referring to los coches naranjas would also be correct. (It should be noted that in some areas the adjective anaranjado also is frequently used for "orange").
A final note on invariable adjectives: As indicated above, macho and hembra are probably the common traditionally invariable adjectives (although you will often hear them made plural, perhaps more often than not). Others of more recent use include monstruo (monster) and modelo (model).
Almost all of the other invariable adjectives you'll come across are either proper names (such as Wright in los hermanos Wright, "the Wright brothers," or Burger King in los restaurantes Burger King) or adjectives borrowed from foreign languages. Examples of the latter include web as in las páginas web for "the web pages" and sport as in los coches sport for "the sports cars."