What determines when a virus becomes a "new strain"?
I don't know if this is a comprehensive enough answer, but viruses are taxonomically broken down into order (-virales), family (-viridae), subfamily (-virinae), genus (-virus) and species. This system was developed by the ICTV and is concurrently used with the Baltimore System.

A lot of species contain variations called virus strains. There are two types, serotype and genotype.

In serotypes, the differences are detected by variation in antigens. Genotypes are detected by differences in genome sequence.(1).

The reason a vaccine is difficult to create for the common cold, or upper respiratory tract infections is not only because of the frequency of mutation but also due to the large number of serotypes present.(2),(3).


Virology: Principles and Applications - Carter.
Princuples and Practice of Infectious Diseases - Mendell, et al.
E.g. Olszewska, et al. Development of vaccines against common colds. Br Med Bull. 2002. 62(1):99-111.