ssh client not working on WPA auth 802.11b/g/n wireless network

When using a new router that uses WPA/WPA2 authentication, I am unable to ssh out to an external server

I am able to connect when I use wired connection.
The internet connection seems to drop a lot as well but is more usable.
I can use ssh from other OS' over wifi (Tried putty on Windows7 and prompt on iOS).
When I go back to the old router which uses WEP it works fine again.
The only other difference between the routers is the newer one is 802.11b/g/n whereas the old one is just 802.11b/g.

Any ideas on how to solve this problem?

This is the output when I use ssh -vv
$ ssh -vv <email address hidden>
OpenSSH_5.3p1 Debian-3ubuntu7, OpenSSL 0.9.8k 25 Mar 2009
debug1: Reading configuration data /home/anna/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to xxx.xxx.xxx.xxx [xxx.xxx.xxx.xxx] port 22.
debug1: Connection established.
debug1: identity file /home/anna/.ssh/identity type -1
debug2: key_type_from_name: unknown key type '-----BEGIN'
debug2: key_type_from_name: unknown key type '-----END'
debug1: identity file /home/anna/.ssh/id_rsa type 1
debug1: Checking blacklist file /usr/share/ssh/blacklist.RSA-2048
debug1: Checking blacklist file /etc/ssh/blacklist.RSA-2048
debug1: identity file /home/anna/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.3p1 Debian-3ubuntu7
debug2: fd 3 setting O_NONBLOCK
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,<email address hidden>,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,<email address hidden>,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,<email address hidden>,zlib
debug2: kex_parse_kexinit: none,<email address hidden>,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha256,diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,aes192-cbc,aes256-cbc,arcfour,<email address hidden>
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,<email address hidden>,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,<email address hidden>,hmac-ripemd160,<email address hidden>,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,<email address hidden>
debug2: kex_parse_kexinit: none,<email address hidden>
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: mac_setup: found hmac-md5
debug1: kex: server->client aes128-ctr hmac-md5 none
debug2: mac_setup: found hmac-md5
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
Connection closed by xxx.xxx.xxx.xxx

relevant output from lspci:

03:00.0 Network controller [0280]: Realtek Semiconductor Co., Ltd. Device [10ec:8172] (rev 10)
 Subsystem: Realtek Semiconductor Co., Ltd. Device [10ec:e020]
 Flags: bus master, fast devsel, latency 0, IRQ 19
 I/O ports at b000 [size=256]
 Memory at d0300000 (32-bit, non-prefetchable) [size=16K]
 Capabilities: <access denied>
 Kernel driver in use: rtl819xSE
 Kernel modules: rtl8192se, r8192se_pci

$ iwconfig wlan0
wlan0 802.11bgn ESSID:"O2wirelessF934A7" Nickname:"rtl8191SEVA2"
          Mode:Managed Frequency=2.462 GHz Access Point: 00:26:44:F9:34:A7
          Bit Rate=39 Mb/s
          Retry:on RTS thr:off Fragment thr:off
          Power Management period:0us mode:All packets received
          Link Quality=50/100 Signal level=-81 dBm Noise level=-95 dBm
          Rx invalid nwid:0 Rx invalid crypt:0 Rx invalid frag:0
          Tx excessive retries:0 Invalid misc:0 Missed beacon:0

Distribution Ubuntu 10.04
Architecture i386
Kernel Linux 2.6.32-38-generic i686
OpenSSH_5.3p1 Debian-3ubuntu7
wireless-tools 30~pre9-3ubuntu4
wpasupplicant 0.6.9-3ubuntu3