Replacing the 72 pin connector can sort it however you will find if your getting grey or garbled graphics it's probably crud on the carts. Best thing to do is buy a cleaning kit off the net that contains two solutions. One is white and removes the built up crud the second is a weak alcohol that removes the white stuff and any remaining crud. You will also need to a special bit to remove the screws in the cart case.
When openening the carts pay special attention to how the PCB fits in the plastic case. You need to make sure it goes back in the right way.
Also the new 72 pin connector can be tight when first used. It is reccomended to start with cleaned newer carts before using some of the older, launch titles. the older carts used a thicker pcb that could wreck the new 72 pin connector. It rare for it to happen but it's best to start with newer carts because the pcb is thinner and helps break in the 72 pin connector. Also don't leave carts in over night because undue stress on the connectors can cause damage over time.