Okay so the conclusion was that you cannot deploy with MARS. You need to run Luna. We had success with the 32bit version of Luna. Installing the 'Eclipse Java Developer Tools' and FRC plugins from Luna took more than an hour. They ran extremely slow, but just be patient and they will eventually finish. I found that I could download eclipse from here much faster than from the eclipse.org site:
http://ftp.acc.umu.se/mirror/eclipse...ease/luna/SR2/