Ubuntu – Turning on UFW stops the e-mail client functioning (both imap and smtp) even though they are allowed

I am using ubuntu 10.04 on a VPS. Without enabling UFW everythign works fine – imap using port 143. And sends emails using smtp port 587.

However, when I turn on UFW a lot of problems are encountered. Email fails, ssh log ins are very slow, and dig command does not work – it times out. Also, Apt-get install does not work.

ufw status verbose returns :

Status: active
Logging: on (low)
Default: deny (incoming), allow (outgoing)
New profiles: skip

To                         Action      From
--                         ------      ----
Anywhere                   ALLOW IN    my.ip.address.0
Anywhere                   ALLOW IN    my.ip.address.0/24
80                         ALLOW IN    Anywhere
443                        ALLOW IN    Anywhere
25/tcp                     ALLOW IN    Anywhere
587                        ALLOW IN    Anywhere
143                        ALLOW IN    Anywhere
993                        ALLOW IN    Anywhere
465/tcp                    ALLOW IN    Anywhere
587/tcp                    ALLOW IN    Anywhere
143/tcp                    ALLOW IN    Anywhere
587/udp                    ALLOW IN    Anywhere
53/tcp                     ALLOW IN    Anywhere
53/udp                     ALLOW IN    Anywhere
68/udp                     ALLOW IN    Anywhere
67/udp                     ALLOW IN    Anywhere
53                         ALLOW IN    Anywhere
53                         ALLOW OUT   Anywhere
53/tcp                     ALLOW OUT   Anywhere
53/udp                     ALLOW OUT   Anywhere

In my syslog I get the following (and same again with port 53 allowed):

Aug 25 13:55:31 VPS##-###-## postfix/smtpd[23611]: NOQUEUE: reject: RCPT from unknown[ip.address.here.0]: 450 4.1.8 <my@gmail.com>: Sender address rejected: Domain not found; from=<my@gmail.com> to=<my@server.com> proto=ESMTP helo=<mail-qy0-f179.google.com>

/var/log/messages does not seem to contain anything relevant even though ufw logging is on