Minecraft is Turing-complete too. You just have to build your own CPU and there's no way you're going to get 100 kHz out of it. Heck, so is Dwarf Fortress. People have built CPUs in both.
Personally, I say the difference is that Notch makes meta-games. That is, he makes game worlds in which people create their own games.
You are absolutely right -- in the sense that even a dead-simple Turing machine built inside one of those other games is Turing complete too.
0x10c feels like a milestone, though... I guess it's because the in-game CPU this time around is usable on a human timescale. If in-game networking is ever added to 0x10c, one could even imagine a usable minecraft clone inside the game. It feels different this time.
Yes, I think it's an important milestone in terms of making that sort of mechanic more available to everyone. Most people were building small, special purpose circuits instead of general purpose devices, simply because it was difficult and wasteful to build your own CPU... unless that was their goal in the first place.
I agree that 0x10^c will likely be something special.
Personally, I say the difference is that Notch makes meta-games. That is, he makes game worlds in which people create their own games.