The Wikipedia article on stellar classification has the full list of letters:
Class | Surface Temperature
O | > 33,000 K
B | 10,000 - 33,000 K
A | 7500 - 10,000 K
F | 6000 - 7500 K
G | 5200 - 6000 K
K | 3700 - 5200 K
M | 2000 - 3700 K
L | 1300 - 2000 K -
T | 700 - 1300 K | These are those new letters
Y | < 700 K -
This Cornell doc explains much of the history behind the system:
In the 1890s, many scientists were interested in developing a classification scheme for the stars. Edward C. Pickering at Harvard University, together with his assistant Williamina P. Fleming, assigned stars a letter according to how much Hydrogen could be observed in their spectra: stars labeled A had the most Hydrogen, B the next most, and so on through the alphabet. There were 22 types in all: this scheme was rather cumbersome, and it wasn't clear what its physical significance was.
In 1901, another of Pickering's assistants, Annie Jump Cannon, also begun to work on the classification sequence. Her meticulous observations led her to simplify the 22-type scheme into a simple sequence of temperature: OBAFGKM. Not only was the scheme much simpler than the previous, but it related the amount of hydrogen observed to a physical property of the stars for the first time.