The fundamental problem is that Excel forces a novice (and actually everyone) to work at a level of detail such that key elements of the plan or analysis are lost in a forest of low level code. I would focus on the novice because it will be hard to get power users to switch. Letting a user pick a range or distribution for an input instead of a specific value will help to avoid anchoring around the "one right answer."

Compare two spreadsheet highlighting changes more intelligently than Excel's. For example, allow for a more intentional representation of

   decisions/numbers/inputs: control variable
   relationships/rules: system representation
   outputs/results: state variable

Track changes to indicate if inputs or rules/relationships changed, optionally ignore output changes

Allow for a set of input variables (and optionally some rules) to be defined as a scenario to compare differences between scenarios. Also, let an input variable be a distribution or an interval and the scenario specify any covariances.

Scenario planning and decision trees: a graphical view that can switch to a traditional spreadsheet view and vice versa.

EDIT http://www.google.com/search?q="next+generation+spreadsheet" turns up some interesting ideas as well.