"Perhaps an Excel replacement will need to have an Excel-like interface..."

Perhaps an Excel replacement will basically be Excel, with a background script/plugin that scrapes that routinely scrapes the data and feeds it into a database. (Hey! Startup idea). The first entry in each column becomes the data field. The program is smart enough to take a sample data from each column, and use that to auto-pick the best data type. (Also re-checks a random sample periodically and re-defines data type if necessary). Bonus points for creating excel templates for consistency ('actions template', 'to-do list template', 'known bugs'....etc. Last one was a joke) and for easier definition of relationships between different spreadsheets (like for like data comparisons and relationships as long as the user enters the right info in the right cell). Now that Office has migrated to the web, this could be entirely web-based.

People's workflow visually to them remains exactly the same, which would overcome the biggest obstacle - unfamiliarity and resistance to change. Non-techies who need to make a list of customers, processes or actions don't know or think about headaches they are creating for themselves or others down the line. It's only the technically literate who would appreciate the problems of consistent, clean data, version control etc. This solution would begin to answer some of those problems.

I think people massively underestimate spreadsheets. I don't think its a matter of them being so dumb that businesses like them - I think the grid metaphor with dataflow processing of values and the integration of code and data make them unparalleled for business use.