A couple of corrections(?) to your post lukemcleod (I have had very similar thoughts).
In the primary universe you travel back in time; you are no longer part of that Universe - you time travelled out of it but arriving in your past you do not change the future you create a new one - a new multiverse system.
That new multiverse edition continues from the time you travelled to with you as an integral part of it. You kill your Grandfather yet you do not disappear for you are from another multiverse where you were born. It is in this new multiverse that you cannot be born as your 'Grandfather' had no offspring. No conflicts anywhere.
No, the difficulty comes with the information loop where, for example the secret of time travel is passed from a future self and no one ever discovered it.