There have been two distinct Kristine Kochanskis (just as there have been two Krytens and two Hollys.) The first, CP Grogan (lead singer for the early-80's band Altered Images), played Krissie from 1988 (Red Dwarf Series 1) through 1996 (Series 6). Chloe Annett (pedantically, "Chloë Annett") has been Konchanski from 1997 (Series 7) to the present.
In the earlier Red Dwarf series, Dave actually never went out with Kochanski, he has only admired her from afar (in Series 1, Dave asks Holly why he brought back Rimmer rather than, say, Kristine Kochanski and Holly says that in Dave's entire life, the sum of all of their conversations was only 173 words.) It was only later on (Series 5? Series 6?) that the meme that the two had been an item came into being.
I still haven't heard any good explanation for this gigantic break in continuity, but I'm sure Rob Grant and Doug Naylor have thought of something. Red Dwarf might not be "Great Science" science fiction (it's not Arthur C. Clarke), but, for the most part, it's always been internally consistent.