First, is the card under warranty? Even if it isn't, a few manufacturers will work with you. Email them. Be polite and professional.
If this is a no-go:
Inspect the wiring solder points. Check the leads on the fan, make sure they aren't loose on the pins. It could be a short.
You can test the fan, but it sounds like the fan controller on the card may be giving out.
To test the fan you will have to figure out what voltage it uses and connect it to another power source and let it run awhile, such as a case fan header on the motherboard. These generally use 12v. Your particular fan on your GPU may only require 5v - it all depends on the size and type of fan. You'll have to look at the label on the fan.
If your fan is bad, then I'd buy a new fan if you can. You may be able to take the heatsink apart and purchase the exact fan online if you search right. Most heatsinks are a combination of aluminum and plastic - they have screws, sometimes they are under the sticker label.
If replacing the small fan is not an option, and you are sure that it IS the fan then replace the heatsink.
