As somebody else previously stated, try doing a full connect scan (-sT) instead of just using the SYN scan. I dont know what it is, but my windows box doesnt like it when a TCP connection isnt fully opened or left hanging in anyways.

Dont use fragmentation (You didnt say you have, but I figured I'd throw this in anyway) I dont know about everybody else, but Windows doesnt seem to deal well with fragmented packets, either receiving OR generating them.

Use the very verbose option (-vv) as this is a good way to see if its even getting the ICMP packets out on the wire. I really dont know why but sometimes it will ping the hosts, but wont initiate the scan. I've also noticed that if you turn off the DNS resolution it will sometimes hang, others it will drastically speed things up.

I have had some problems (and some solutions) with Nmap for Windows. Personally I think it is a buggy piece of ****, but there are ways to get around some of the issues I have found. If your looking for a good reliable scanner for windows I would reccomend IPTools. Hope this helps.

Jonesy