Well I have never been able to get Nmap to work correctly on my win system... I don't know what you are doing wrong on the linux system... Is everything configured correctly?