Cannot see why gmail is marking mail from my server as spam

Hi guys,

I have set up ubuntu 14.04 with iRedMail (iredmail.org) as a mail server and have set up all of the DNS records for sending email (I've included txt record combination spf/dkim in an attempt to ensure everything is correct).

I have sent three emails in total to my two Gmail accounts in order to see if they are marked as spam - and they are - even though the headers seem to indicate they shouldn't be. Here is a pastebin of an example email (I have changed all of the account details, ip addresses etc : http://pastebin.com/3LDceASd)

Google shows the mssage:
> Why is this message in Spam? It's similar to messages that were detected by our spam filters.

I have only created the DKIM record in Namecheap's DNS today, but clearly it's picked up by Google, so I don't think it's that. Although, if I run the command amavisd-new testkeys I get the message:

dkim._domainkey.mydomain.co.uk => invalid (public key: not available)

Admittedly, my knowledge of mail servers is really not that great, hence my using iRedMail which I must admit has served me very well in the past.

If you need any further information to help diagnose, please let me know and I really appreciate any help!

Thanks

edit: according to mail-tester.com, having more than one spf record is bad, so I have now configured the record to just "v=spf1 a:mydomain.co.uk -all"

edit 2: I have also edited /etc/hosts line from 123.456.789.100 mail.mydomain.co.uk to 123.456.789.100 mydomain.co.uk because mail-tester said the "HELO" was mail.mydomain.co.uk. Although if I do hostname -f it returns "mydomain.co.uk" so I could only think it's the hosts file??

I fixed this by editing /etc/postfix/main.cf and finding the line "myhostname = " and setting it to "mydomain.co.uk" instead of "mail.mydomain.co.uk"

edit 3: OK .. so my score is now -3 because it is saying my DKIM is invalid, I followed this guide: https://code.google.com/p/iredmail/wiki/DNS_DKIM, so I guess all I need to know is how do I correctly generate a DKIM?

I'll stop editing now..