Do you have your grandparent's death certificates? if not you can look the references to them up in the IGI (which often lists parents names, but not always) or Births, Deaths and Marriages registers for the area they are believed to have died. The Death certificates usually give both parents names, including the mother's maiden name.
Your parents birth certificates should give the age of your grandparents at the time of your parents birth. This would give you an idea of what years to look for for your grandparents births in the registers. The birth certificates I have also give the place of birth of the parents.