Kell, I think you just hit the nail right on the head. It is really hard to catagorise a book into a particular genre because of all the different elements in books.
As another example, my english teacher said that sci-fi must be set in the future, but Dr Who is (well, predominantley (sp?)) sci-fi, and that isn't always in the future. I think it would be more accurate to say that it must have some futuristic elements, eg the TARDIS, or the sonic screwdriver.
Or, Artemis Fowl. Is that fantasy or sci-fi?