It's a hardy perennial: what makes a book-length act of storytelling count as historical fiction? You'd be surprised at how many different answers there are. Whether a book is historical fiction also depends on whether you're asking as the writer, the reader or the seller of it. So I can't give you fixed answers (no change there, then): we're slithering about in very elemental ideas of space and time and people, here. (And there's a whole other post, some day, in the question of when historical fiction becomes creative life writing.) But here are some ways to think about the issues.
Fiction that uses History because it's distant from us
The Historical Novels Review, for understandable reasons, has tackled this issue, and Sarah Johnson's definition of Historical Fiction is a novel set fifty years ago or more, which the writer is writing from research, not direct knowledge. The Historical Novel Society, on the other hand, has an or where the HNR, implicitly, has an and: "... written at least fifty years after the events described, or have been written by someone who was not alive at the time of those events."
I do think this is the only fundamental, inescapable definition: that it is a novel written about Then, as a world separate and different from Now. Of course, there is a sense in which all novels are historical: they're written "as if" these events are past. But I think there must be some sense of the writer setting out to exploring a time which is long gone, and therefore has a real sense of Otherness about it. Even if your project is to explore the eternal human things, the point is only made if everything else about your characters' lives is different from ours: contingent and particular to their time.
Fiction that explores History as a process
One of the earliest critics of the genre, György Lukács, argues that it's "unarguable" that an historical novel must include real historical events and at least one real historical character (although he agrees with Rose Tremain that the main character must be fictional). I think that's very odd, but it's his Marxist conviction that what matters in human understanding is the processes by which society changes. It's also, arguably, a very "traditional male" view: that what counts as historical is what makes it on to the record - i.e. men's stuff. (The Commentary part of my PhD thesis explores all this further, and if you really want to, you can download it here.)
Historians study change change from one particular state to the next, so they can form general principles about how these things work. Fiction, on the other hand, "resists generalising", as Jane Smiley puts it in Thirteen Ways of Looking At the Novel. That makes trying to use fiction to explain your history book stuff a dangerous game. In real life we are less aware of the big changes that Historizns will notice later, and more aware of the continuities of life in our own small compass. But this is also, perhaps, the place where the novel set in a recent time can work as an historical novel: when the project of the novel is to pinpoint a very clear moment in that big process of real historical change.
But if fiction is rooted in the particular and the individual, that includes the human experience of living in the flow of historical time: our sense of Then is part of our Now. That's why I don't actually think I write historical fiction at all: I write fiction about history, and I'm not alone in that. The parallel narrative is a dead giveaway, of course, but characters coping in a place and time of acute change is another. Just don't make them unconvincingly clairvoyant about the future.
Fiction that uses History as a setting for genre
The classic story-pleasures can be given extra flavour by being imported into another time and place. Historical Crime and Thriller does well at all ends of the literary-commercial spectrum. Historical Adventure is an easy sell because we all know that adventure was far more adventurous in an unwired, indeed unmapped, world. Historical Romance is the one that people are sniffiest about. There is a sense in too many readers, writers and reviewers that if it's swords, sandals and broken bones it's historical fiction, but if it's sewing, slippers and broken hearts it isn't, it's romantic fiction. Which wouldn't matter if people weren't so snobbish about romance as a genre, though in reality every genre has exactly the same ratio of rubbish (and un-historical rubbish at that) to good stuff. On the other hand I am - apparently - unquestionably a historical novelist, despite the fact that at the heart of most of my stories are characters falling in and out of love and bed and wedlock. Maybe it was the death by being shot through the liver at the siege of Badajoz which got me in.
On the other hand, under the broad umbrella of Women's Fiction, Historical Drama is very welcome indeed, as it's so rich in possibilities for one of fiction's most honourable functions: that of giving voice to the voiceless. And, as ever, once you get into literary fiction, all the boundaries of genre and plot begin to melt and run: Wolf Hall is discussed as fiction by many who would never say they read historical fiction.
Fiction that uses a period of History as a character
For the writer, it's often the smell of a place and time that first hooks us, and then we look for a character and story to embody it. But a couple of years ago I heard a bookseller saying that the Second World War had only just "become historical fiction". In other words it was an era that, for the readers of fiction, had only now acquired its own personality, as a particular country has a personality that visitors seek. I assume this is because few are still alive who lived through 1939-46 as an adult. Readers' sense of the period is mediated through (grand)parents, school, non-fiction, documentaries, gift shops, music, re-enactments. That's what readies readers for us, with our stories which are one step away from those "facts": a whole story which never actually happened.
The thing is, to sell a book you have to convey what the book will give the reader, and "This book is set in a period which means nothing to you but I promise it's really interesting", is always going to be a tougher sell (believe me, I've tried) than "This book is set in Tudor/the WW1 Trenches/Napoleonic times", or one of the other periods which we're fed by school and films and national myth. On the other hand, where you can draw on readers' existing tastes, but push beyond their edges, there's lots of potential. A Secret Alchemy's Wars of the Roses setting is every bit as glamorous and violent as Tudor times, but less well-trodden territory: that was part of what drew me to the period, and it did the same for readers.
The analogies between space and time always crop up when you're talking about this stuff. The past is a foreign country, as L P Hartley says: they do things differently there. Readers have to have acquired some sense of what that country is, before they will want to travel in it.
So the writer has to learn and imagine how they did things in that foreign country, and then write it. For writers, the most fundamental definition is therefore Margaret Atwood's: that it's a novel set "before the writer came to consciousness". In other words, you can't be drawing on direct experience to write that world. It's this business of turning the "inert data" of researched material into a fully re-imagined, living, breathing world, as Rose Tremain puts it, which conditions the process of writing the novel, far more than the date it's set in. (That's why we have so much in common with the writers of speculative fiction: none of us can actually have been to the world that we're writing).
To my 1990s-born children, the 1976 strand of The Mathematics of Love is almost as historically Other (no mobile phones and no internet) as the 1819 strand would have been to my 1901-born grandmother (no trains and no telegraph). Readers read for that sense of Then, for the foreignness, and that's not a matter of adding up years, that's about defamiliarising. But it's also about finding the Now in the Then: readers are always, also, reading about their own time and place.