What happens when additional costs can't ultimately be paid, but the spell is on the stack?
When the opponents gets a chance to cast Terror, the Goblin has already been sacrificed as part of the cost to cast Goblin Grenade. It's not available to be targetted by Terror.



Additional costs are part of the total cost to cast a spell or activate an ability. To paraphrase 601.2e,


  total cost = mana cost or alternative cost + cost increases and additional costs - cost reductions


The total cost to cast a spell is payed as part of casting the spell. To paraphrase 601.2's subsections, to cast a spell is to


(601.2a) Place the card on the stack.
(601.2b-d) Make some choices including targets.
(601.2e) Determine the total cost to cast the spell.
(601.2f) Activate mana abilities.
(601.2g) Pay the total cost to cast the spell.


All of this, including sacrificing a Goblin, happens when you cast Goblin Grenade. When the opponents gets a chance to cast Terror, the Goblin has already been sacrificed.

The illegal action in your scenario is the casting of Goblin Grenade for the wrong cost. In a casual setting, you should rewind the casting of Terror, finish paying the cost of Goblin Grenade (i.e. Sacrifice a Goblin), then proceed from there.

Things are different at Pro and Competitive Rule Enforcement Levels (REL). For starters, there would be two errors. You failed to pay the appropriate cost (Game Play Error — Game Rule Violation) , and your opponent allowed the game to proceed in a bad state (Game Play Error — Failure to Maintain Game State). The consequences are detailed in the Infraction Procedure Guide (IPG) rather than CR 717.1.