i just heard back from Travis support: they have found a fix and are currently testing it before rolling it out.
For the impatient among you: there is a workaround, which involves adding the following to your .travis.yml:
before_install:
- |
sudo tee /etc/resolvconf/resolv.conf.d/tail <<EOF
options attempts:5
EOF
- sudo service resolvconf restart