I’ve met the same problem those days, after tens of trials I found that this error is caused by the Ubuntu distribution used by task. For the one you stated as “working”, it’s running on trusty, and the errored one was running on xenial.
TO FIX THIS, add the following code to your .travis.yml file,
dist: trusty
To manually appoint the Ubuntu distribution version.
trusty is trusty for real