The only thing to watch when overclocking is that things like serial comms ad the like often wont work. I had an 18F4580 running on a 20Mhz xtal with the HS_PLL setting - whilst it wasn't probably running at 80Mhz, it was dammed fast - but non of my serial comms would work until I replaced the 20Mhz xtal with a 12Mhz one. (as spotted by Alain)

I was going to suggest that you tried using the xtal from the breadboard that you know was a proven crystal... but now you seem to of resolved the problem. - I have to agree with Alain, I would only purchase from a large component retailer (RS in my case).