No issues to speak of so far. Our app databases are in the VPC itself so our own traffic does not get routed through the NAT gateway but I haven't heard any issues from users either.

At the moment we're using an m1.small for the NAT itself though if you have perf issues you can bump that up as well. I would guess a c1.medium would be more appropriate though as I said we haven't had any issues so haven't considered changing anything yet.

Here's a speed test through from a m1.small through the NAT (27.5 MB/s):

    $ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
      % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                     Dload  Upload   Total   Spent    Left  Speed
    100  500M  100  500M    0     0  27.5M      0  0:00:18  0:00:18 --:--:-- 29.2M

Here's a speed test from a m1.small vanilla EC2 instance outside the NAT (38.2 MB/s):

    $ curl -o /dev/null http://speedtest.wdc01.softlayer.com/downloads/test500.zip
      % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                     Dload  Upload   Total   Spent    Left  Speed
    100  500M  100  500M    0     0  38.2M      0  0:00:13  0:00:13 --:--:-- 34.1M