How does agile work when replacing a working system?

Question

In an ideal Agile world, you quickly build a small, but useful subset of the desired end system, and give it to users. They're excited, because it's useful, they start using it and give feedback. You then work out what to add on to it, build that, and repeat until you run out of time.

I've had a couple of projects recently that involved replacing some kind of working system. The above model just didn't work at all: until you'd built a system that included virtually all the functionality of the existing system, users had no interest at all. They wouldn't use it.

How do you apply Agile when "the smallest useful subset" is "all of it"?