I think that "дед да баба" does not necessarily mean "a grandpa and grandma". I don't think there were any grandchildren mentioned in the tale.

The word "дед" means "an old man" and "баба" means simply "a spouse", or more generally "a woman". Who knows, maybe the old man had a younger spouse?

So, I suggest translating "Жили-были дед да баба" at least as "Once upon a time there was an old couple".