I had practically this same exact problem a few weeks ago. Asus Sabertooth Z77, i5-3570K, using the stock intel cooler. It worked fine for about a day and then the fan just wouldn't spin up. After that I kept getting CPU FAN errors every time I tried to boot up.
I never did find out what the problem was, but after installing an aftermarket fan and heatsink the problem went away. I noticed my new fan only has a 3 pin wire, while the intel one had 4 pins. I have no idea if this had something to do with it. The weird thing is that, like you when I plugged it into one of the other headers, the fan spins fine, but the motherboard doesn't acknowledge it's presence. That seems to imply the fan itself is fine and the motherboard is at fault... Anyway, I wish you luck with it. If your problem is the same as mine, a new heatsink + fan should fix it. I got myself a nice Noctua to replace it.
Well if your CPU isn't needing any cooling than your fan won't spin up. I wouldn't worry about it unless you put the system under load and then doesn't spin up.
Yeah... I'm going to have to disagree with that one lunyone. Even at idle the CPU heats up, if you plan on running anything more complex than YouTube you are definitely going to need some cooling on it. Good air flow on the inside of the case can only go so far, you need to get the air moving onto the CPU heatsink. I wouldn't risk letting the computer boot up if the CPU fan isn't spinning.
EDIT: I did take his suggestion to test the stock Intel fan on it's own... it does seem to spin up. I really think it's some kind of issue with the motherboard. I just can't be bothered to pack it up and send it all the way back to the supplier... The computer is working now, and that whole process would probably take weeks.