Let $(M,g)$ be a closed, compact Riemannian manifold. Let $P$ be a $2r$th order pseudodifferential operator, where $r \in \Bbb{R}_+$. Suppose that the differential equation $Pu=f$ has a unique $H^r(M)$ solution for all $f$ in the dual space of $H^r(M)$. Does it follow that $P$ is elliptic?
Yes, this is correct. You can find a more general result in
More precisely see Corollary 1, Chap. IV, page 251 in the above reference. 

