The Visual Studio team overcame a similar problem with a complete rewrite. I think the problem is more about breaking the compatibility, many add-ins rely to a very old COM interface. But I think people wouldn't mind a breaking change if it comes with really new and powerful capabilities. In fact it would provide an incentive to upgrade. And it can run side by side with old-style spreadsheets that preserve compatibility.
The problem is not so much large datasets, for which there are better tools than Excel. It has more to do with doing more advanced thing conceptually.
For instance, what about adding a table to a sheet (Apple Calcs style), specifying a name and some inputs cells, and one output cell or range, and then being able to use that table as a function anywhere else in the workbook. I can already solve these types of problems with a UDF, but think about users who do not know how to code. Also, having the logic of a function in excel formula format makes it easily auditable by a non-programmer.
And also what about manipulating data in memory instead of having everything in big sheets and having to link every cell with each other, or having nested tables in a cell (or a reference to a table in memory or in another sheet).
And this is Excel only. Word and PowerPoint should really have a mark-up language side by side with the visual representation. That would make it so much easier to manage metadata (object names, linking a piece of text to an external source, working with templates, etc).