Are you on some kind of broadband connection like DSL or cable modem behind a lynksys router/modem? Is it running NAT for you so you actually only have a private IP address and the router has a real address? Are you trying to nmap a machine that's not on your local network?
If you answered yes to most of these questions, I can see it not working. Most NAT devices won't pass that kind of traffic back to you.