After much digging around I finally found the issue, as I am using Frankfurt for my S3 backup.
The problem is that when installing Mailinabox on a new box the BOTO package is correctly installed for Python 3, but not for Python 2 that Duplicity uses.
Installing it from the repository does not solve the problem for me as an old version of BOTO is provided, so to fix the problem I proceeded in the following way:
As Root:
apt-get purge python-boto
this will remove the ubuntu-provided old boto if you tried the solution from damowhite232
git clone git://github.com/boto/boto.git cd boto python setup.py install
This will install the last boto release in Python 2.7 allowing to backup and restore from S3 Frankfurt
EDIT: Thanks to nstanke on Github, there’s a cleaner solution / workaround: