Wouldn't be any issues with Software Serial or anything else with this increase in speed?
Yes. UART timing, delay(), delayMilliseconds() and millis() timing, as well as the bootloader I mentioned before.
The bootloader is the showstopper, as it requires a hardware programmer to change it. One of the big attractions of the Arduino is that you don't need the external hardware programmer, and I would guess most Arduino users don't have one. Combine this with the fact that most folks don't need the extra speed, and you just don't see a lot of interest in changing the clock rate.
There's a 20MHz bootloader out there, and programmers of varying cost. If you really need 20MHz it's within reach.
-j