adam, it's indeed doable, and it's what happened with MMX and SSE/SSE2, 3DNOW! and such. Thing is, neither of these are general-purpose instruction sets, and extending the general-purpose sets would require ugly hacks, perhaps prefix bytes or something like that. And then it would only benefit a very small amount of software, since people wouldn't write generic programs to use the extended instructionset until 90% of the market had CPUs supporting it. This is also one of the problems with SSE and such - not to mention that it's a bit more complex optimizing your algorithms for the extended instructionsets, than slamcoding them with normal x86 instructions :)
adamjjackson, AMD has also added (doubled) the number of general purpose registers in their x86-64 architecture. It has been a slow process to get where we are now. With sufficient software abstractions, going forward we should see an increase in adoption of new architectures, imho.