Go for it. It is pretty easy to remove GPU coolers to get at the chip. I have been replacing the thermal paste on every video card that I get. So far, I have only had one where it made a huge difference but I think every now and then you can come across a video card where it wasn't applied correctly.
Have you had this card for a while? While you have it apart, you should clean the dust out of the HS so you get better airflow too.