One of the unfortunate problems with Teredo is that it completely bypasses your network firewall. A typical NAT router also has a stateful firewall that blocks inbound connections except on ports that have explicitly been forwarded. With Teredo, computers on the network have a public IPv6 address. They can accept and initiate connections on any port without the firewall being aware of it. All that the firewall sees when a remote IPv6 host makes a connection to the IPv6 machine on the local network is an inbound packet in a connection initiated by the local machine.
This is no more of a problem than if machines run something like TOR, or a VPN client, but it gives headaches to some network administrators. Of course, the correct solution is to run 6to4 on the router, IPv6 internally, and then use the same firewall settings for IPv6 as for IPv4. This, unfortunately, requires some effort.
The other security problem is psychological. For the last few years a lot of consumer-grade router manufacturers have put NAT as a bullet point under the heading of security. This leads users[md]and some people who should know better[md]to regard NAT as a security feature. A typical IPv6 configuration, however, does not use NAT.
Is it less secure? To answer that, you first need to understand how NAT gets confused with security in the first place. NAT just stands for network address translation, and encompasses a variety of transformations. In a NAT system (of any form), packets sent to one address and port arrive at a machine with another address and/or port. The most common use of this is to allow multiple machines to share a single public IPv4 address. Whenever a machine behind the NAT router sends a packet to an outside host, it is assigned a new port on the public IP address. All packets arriving on that port are forwarded back to the port and host for the original outbound packet.
The NAT part doesn't provide any security, but one of its side effects does. Because ports on the public IP address are only opened when something inside the network tries to send packets out, nothing outside the network can make inbound connections. This is equivalent to a firewall with a default deny policy.
This security is completely orthogonal to the NAT aspect. Some routers[md]for example, some older 3Com products[md]had NAT but without this policy. They designated a single machine as the default recipient for any inbound packets. If you tried to connect to the public IP on port 80, your packets would be forwarded to the default host's port 80. This let you, for example, access Windows fileshares from the Internet[md]clearly a bad idea. Newer NAT devices require explicit port forwarding to do this, but that's equivalent on a non-NAT'd network to simply opening the port.
In fact, NAT reduces security. There is an entire category of port rebinding attacks that only affect NAT. Because the NAT router has a limited number of ports to use, sometimes it reuses them. This can result in packets being delivered to the wrong host.