Solution:
First, we characterize all ordered pairs of general (not necessarily odd) positive integers $(m, n)$ such that $\gcd (4^{m} + 2^{m} + 1, 4^{n} + 2^{n} + 1) > 1$. We claim that $(m, n)$ works if and only if either
- $m$ and $n$ are both even, or
- $\nu_{3}(m) = \nu_{3}(n)$.

Proof of necessity. Suppose that $p$ is a prime that divides both $4^{m} + 2^{m} + 1$ and $4^{n} + 2^{n} + 1$. If $p = 3$, $m$ and $n$ must both be even. Henceforth assume that $p \neq 3$. Let $d$ be the order of $2$ modulo $p$. Then, as $p \mid 2^{3m} - 1$, we find that $d \mid 3m$. Furthermore, we cannot have $p \mid 2^{m} - 1$. Otherwise, by lifting the exponent (and $p \neq 3$),
$$\nu_{p}(2^{3m} - 1) = \nu_{p}(2^{m} - 1) + \nu_{p}(3) = \nu_{p}(2^{m} - 1) \implies \nu_{p}(4^{m} + 2^{m} + 1) = 0.$$
The previous two results imply $\nu_{3}(d) = \nu_{3}(m) + 1$. Similarly, $\nu_{3}(d) = \nu_{3}(n) + 1$, so $\nu_{3}(m) = \nu_{3}(n)$.

Proof of sufficiency. If $m$ and $n$ are both even, then $3$ divides both $4^{m} + 2^{m} + 1$ and $4^{n} + 2^{n} + 1$. If $\nu_{3}(m) = \nu_{3}(n) = k$, then we claim that $4^{3^{k}} + 2^{3^{k}} + 1$ divides both $4^{m} + 2^{m} + 1$ and $4^{n} + 2^{n} + 1$. Indeed, note that as polynomials, $x^{2} + x + 1$ divides $x^{2\ell} + x^{\ell} + 1$ when $3 \nmid \ell$. Plugging in $x = 2^{3^{k}}$ with $\ell = m / 3^{k}$ and $\ell = n / 3^{k}$ yields the desired result.

Answer Extraction. We count pairs of odd integers $(m,n)$ less than $80$ with $\nu_{3}(m) = \nu_{3}(n)$. Of all integers in the set $\{1,3,5,\ldots ,79\}$, there are $27$, $9$, $3$, and $1$ of them that have $\nu_{3}$ equal to $0$, $1$, $2$, and $3$, respectively. Hence, the answer is $27^{2} + 9^{2} + 3^{2} + 1^{2} = 820$.