In general, it will probably run with the same code but different crystal. Perhaps you meant that you have to change any timing related code to get correct results. You might need to change the osc config bits as well if going from a 4 mhz to 20 mhz. Also, on the 18F line, you might have to change the PLL setting.
Some crystal frequencies are selected to divide down evenly for things like baud rates (18.432M). 13.5M is a from DVD player's master clock. 14.31818 is common on VGA cards and used for NTSC color subcarrier (div by 4).
edit: by the way, you can overclock a lot of PICs. The guys are sparkfun have an article on it. They got to something like 32mhz before they gave up. I don't know if it causes damage - probably not - but I'd check out all the functions to make sure they aren't affected.