There's nothing more annoying than a fan that has been working fine, then suddenly becomes noisy! This also means it's probably not cooling as well as it should. If cleaning it doesn't help, then oiling the bearing might...
RMA?
If you've found the noisy fan to be on your new graphics card, motherboard, etc, then I recommend you send it back rather than start dismantling it. However, it is, of course, up to you!
Oiling
I picked up somewhere (can't remember where) that oiling a fan can get rid of any nasty noises it is making. It has proved to be quite useful, making several of my smaller sleeve bearing fans a lot quieter. I don't know how well this will work on larger or ball-bearing fans, but if somebody finds out, let me know. Mgh0 now informs me that this has worked for him on 120mm fans. If the fan has actually seized, then oiling it is unlikely to help.
Here we see the subject of this guide. It's a 50mm sleeve bearing fan, the perfect example!
The first thing you have to do is find the side of the fan on which the blade assembly is attached to the rest of the fan (that side is facing up in the picture.) There will be a sticker in the middle - it's not just there for show. Peel it off.
Voila, this reveals where the shaft from the motor attaches to the casing. Now, you need to put a drop (and just a drop) of oil in the yellow highlighted area. Put any more in an it'll get messy! Also, I recommend against using WD40 as it's too thin and might even make the situation worse - use something thicker if you can.
Once oiled, simply cover the hole back up again. Use the original sticker if you can, but I find they've usually lost their stickiness, so I resort to cunning sticky-tape cutting.
I hope this comes in handy!