if you are using a normal computer type fan (12v, approx 200ma or there abouts...) then the NTD4906N is overkill. It can handle 55A.
Either way, it will still work, so your fault is elsewhere, not with your choice of mosfet, the mosfet is fine. Even your other mosfet you mentioned, NDS351AN will work fine.
If you draw up exactly every component you have and how it is hooked up maybe we can help you further... Don't rule out the possibility of the IC being faulty/fried, have you got a spare?