I'm assuming you have the A8N-SLI deluxe because the premium has a heatpipe design. Anyways, the Deluxe's originally had issues w/ the fans not working. But I heard they were fixed. You obviously got an old one.
You can either RMA to Asus or replace the fan yourself.
I personally would just replace the fan myself. Faster, easier, and probably cheaper.
Whatever you do, do it quick. A heatsink without a fan is dangerous.