We obtain the band edge eigenstates and the mid-band states for the complex,
PT-invariant generalized associated Lam\'e potentials $V^{PT}(x)=-a(a+1)m
\sn^2(y,m)-b(b+1)m {\sn^2 (y+K(m),m)} -f(f+1)m {\sn^2
(y+K(m)+iK'(m),m)}-g(g+1)m {\sn^2 (y+iK'(m),m)}$, where $y \equiv ix+\beta$,
and there are four parameters $a,b,f,g$. This work is a substantial
generalization of previous work with the associated Lam\'e potentials
$V(x)=a(a+1)m\sn^2(x,m)+b(b+1)m{\sn^2 (x+K(m),m)}$ and their corresponding
PT-invariant counterparts $V^{PT}(x)=-V(ix+\beta)$, both of which involving
just two parameters $a,b$. We show that for many integer values of $a,b,f,g$,
the PT-invariant potentials $V^{PT}(x)$ are periodic problems with a finite
number of band gaps. Further, usingsupersymmetry, we construct several
additional, new, complex, PT-invariant, periodic potentials with a finite
number of band gaps. We also point out the intimate connection between the
above generalized associated Lam\'e potential problem and Heun's differential
equation.