The following statement appears as a remark in "An Analytic Criterion for the Completeness of Riemannian Manifolds" by William Gordon (1973):
Let $g$ and $\tilde{g}$ be two metric tensors on a smooth manifold $M$. It is trivial to verify that $M$ is complete with respect to $\tilde{g}$ if $M$ is complete with respect to $g$ and $(\tilde{g}_{ij} - g_{ij})$ is positive semidefinite at every point.
Here is how I argued:
It is clear that $\tilde{g}(X, X) \ge g(X, X)$ for all $X \in TM$, from which it is easily seen that $\tilde{d}(p, q) \ge d(p, q)$ for all $p,q \in M$, where $\tilde{d}, d$ are the Riemannian distances induced by $\tilde{g}$, $g$, respectively. Suppose that $(p_n) \subset M$ is a Cauchy sequence with respect to $\tilde{d}$. It follows immediately that $(p_n)$ is Cauchy with respect to $d$, so that the sequence converges to some $p \in M$ by completeness.
Fix $\epsilon > 0$ and consider the compact set $K = \{(x, v) \in TM \ \vert \ d(p, x) \le \epsilon, \ \|v\|_g = \epsilon\}$. Since $\tilde{g}$ is continuous and non-vanishing on $K$, it follows that $\tilde{g}$ is bounded above and below by positive constants on $K$. By homogeneity, there exists $c, C > 0$ such that
$$c\|v\|_g \le \|v\|_{\tilde{g}} \le C\|v\|_g$$
for all $x \in \bar{B}_{\epsilon}(p)$ and $v \in T_x M$. Moreover, it is clear that $C \ge 1$. Now suppose that $x \in B_{\epsilon/C}(p) \subset B_{\epsilon}(p)$. By completeness, there exists a geodesic $\gamma: [0, 1] \to M$ such that $\gamma(0) = x$, $\gamma(1) = p$, and $L(\gamma) = d(p, x)$, where $L$ denotes the length functional induced by $g$. It is clear from the triangle inequality that the image of $\gamma$ is contained within $B_{\epsilon/C}(p)$, so that
$$\tilde{d}(p, x) \le \tilde{L}(\gamma) \le C L(\gamma) = Cd(p, x) < \epsilon.$$
That is, $\tilde{d}(p, x) < \epsilon$ whenever $d(p, x) < \epsilon/C$. The conclusion follows immediately upon choosing $N$ such that $n > N$ implies $d(p_n, p) < \epsilon/C$.
I believe my proof works (though a second opinion is always helpful), but my main question here is what "trivial" proof could Gordon have had in mind? While my proof isn't particularly long, I certainly wouldn't call it trivial. It took me a couple of hours to come up with the strategy of using Lipschitz equivalency and work out the kinks. It doesn't seem to me that bounding $d(p_n, p)$ leads to bounding $\tilde{d}(p_n, p)$ in any sort of controlled way without resulting to a similar argument. Moreover, the topology induced by $d$ is coarser than that induced by $\tilde{d}$, so I don't expect a topological argument to be successful here.
If I had to guess, I suspect Gordon's train of thought is something like what follows.
Lemma. Let $(M, \tau)$ be a topological space, and $d, \widetilde{d} \colon M \times M \to \mathbb{R}$ be two metrics that induce the same topology $\tau$ such that $d$ is complete and $\widetilde{d} \geq d$. Then $\widetilde{d}$ is also complete.
Proof. If $(x_n)_{n=1}^{\infty}$ is a Cauchy sequence under $\widetilde{d}$, then it is also a Cauchy sequence under $d$ and thus converges (in $M$).
Since $\widetilde{g} - g \geq 0$, the conclusion follows. Specifically, fix $x,y \in M$ and consider an arbitrary smooth curve $\gamma \colon I \to M$ connecting $x$ and $y$. Then
$$ \operatorname{length}(\gamma; \widetilde{g}) = \int_{I} \widetilde{g}(\gamma', \gamma') \, \mathrm{d}t \geq \int_{I} g(\gamma', \gamma') \, \mathrm{d}t = \operatorname{length}(\gamma; g).$$
Taking the infimum yields $\widetilde{d}(x,y) \geq d(x,y)$.