I thought I'd add my experience with this.
I too had the problems with the fan, and removed it only to find everything completely clean. I asked the Nissan dealer, and they said it could be a fuse, or the motor could be bad. They could check it for their diagnostic fee. I declined. I took the motor out again, this time hooked it up and tried it. It seemed to spin, but not with a huge amount of power.
So I took the chance and ordered the blower motor, which now ends up at $200 with tax. And worried that it was the fuse and I wasted $200 because I couldn't return a special order item.
It was easy to replace, put it right back in, turned the A/C on and it was cold again! So it was the blower motor, and I noticed the new one has a different part number, so maybe it has been redesigned slightly.
But it was easy enough to pull the glove compartment and get it switched with the helpful photos in this thread. The only place I had a bit of a problem was removing the Glove Compartment Light, I thought I broke it but found that the little tab just hadn't snapped back out.