I should have said that you will likely see strange problems sooner or later if you block all ICMP. You will surely at some point run into certain sites that you will not be able to communicate with at all and you may think that the remote site is down when in fact it's not down.
ICMP performs functions like determining whether the packets going to/from your machine need to be fragmented or not. If the remote end is running larger frame sizes than you (MTU or Maximum Transmission Unit) and your machine can't tell the routers in between that your MTU is only 1500 then the remote site will/may assume that you are capable of the larger frame sizes.
You will run into this if the remote site is running Token Ring, ATM, etc and you are on Ethernet and the DF (don't fragment) bit is set in the packets. Of course this is just one example of a problem that you can have by blocking all ICMP, there are other reasons.
I'm not saying that you should leave ICMP wide open, in fact I would recommend blocking some of it, just that you shouldn't block it completely. It may take a little research to determine exactly what ICMP you should and shouldn't block.