Clear the Travis cache.
You were previously installing vctrs with Apt. So some dependent packages that were installed from source (and cached) are still present (thus their dependency trees are not checked) but their dependencies have suddenly gone missing once you stopped installing those packages from Apt.