NAT это скалка в одном месте для пиринговых сетей, а скайп как раз пиринговая сеть. Перед создателем пиринговой сети стоит задача предусмотреть методы обхода НАТ. К примеру проброс портов с помощью UPNP или начать передавать трафик пользователей через кого то ещё, или ещё что-то придумать (иногда способы действуют только для одного из видов НАТ). Если в конце концов никакими хитростями не получается обойти, то передают трафик через кого-то, а он может даже этого и не знает. Если у него платный трафик то ему будет потом очень весело

Но этого кого-то надо ещё найти и желательно он не должен сильно увеличивать путь трафика, иначе при передачи будут заметные задержки. А что если он взял и загрузил свой канал по полной ? И этого кого-то должно быть несколько, так как один из них может вдруг пропасть из сети. После того как мы выбрали через кого будет идти трафик, мы должны дать знать всем остальным что-бы они его не перегрузили, ведь его трафик не безграничный. Но что если в тот момент как мы его выбрали, его выбрал кто-то ещё, и нам больше нету места ? А что если тех кто находится за нат намного больше чем тех кто имеет прямое подключение, тогда найти через кого можно пустить трафик может быть большой проблемой.
Скайп вполне мог тормозить из за НАТ, и такие жалобы часто случаются. По этому у него есть дополнительные настройки для того чтобы обойти его
http://forum.skype.com/index.php?showtopic=683363.
Хотя нат может быть и не причём. Вот
http://www.skypeclub.ru/viewtopic.php?t=6771 человек убедился что проброс портов через нат работает, но скайп всё равно тормозит, а роутер у него такой же.
Если причина не в нат, тогда остаётся только QoS или плохой wi-fi линк. Для того что-бы проверить линк пропингуй роутер через вайфай, сеть должна быть не нагруженной. Если пинг большой значит проблема в wi-fi соеденении.
Если это
QoS, тогда можно попробовать не официальные прошивки (естественно на свой страх и риск).