I phoned 505games tech support - UK 0870 600 1698
The person I spoke to said to look in the registry under HKEY_LOCAL_MACHINE - SOFTWARE - Bohemia Interactive Studio - ArmA and to make sure the KEY (REG_BINARY) was what was printed in the manual. It wasn't so he told me to change the text. When I tried it wouldn't enter the letters and numbers that I typed.
He then said to re-install making sure my Antivirus was disabled and if that doesn't work return the game to Amazon.
I reinstalled with my antivirus disabled and I can now connect seven times out of the eight times I've tried.
UPDATE: I restarted the game and now I'm getting the Invalid CD Key error (usually followed by letters or numbers which are different everytime I get the error) on every server I try.