Nat firewalls will only block incoming connections... They won't block outgoing connections. For this reason, most people will reccommend something like Personal Firewall or Zone Alarm as well. It's definately much more secure than no firewall. Personally, I don't use firewall software, just the NAT based router, but on the other computers in my house for other people have it on.
Trojans and worms could be built to get around NAT based firewalls, although it does put the creator at risk, because the program will have to be hard coded to establish an outgoing connection. I don't know if there are any that do this right now... Maybe someone else can elaborate a little more.