To clarify Qiaochu's comment and make it explicit, I claim there are uncountably many languages with a rational generating function (namely, $\dfrac{1}{1-x}$). Only countably many of these can even be recursively enumerable. Namely, let $w\in \lbrace 0,1\rbrace^{\omega}$ be a right infinite word. Let $L(w)$ be the language of prefixes of $w$. Then $L(w)$ has a unique element of length $n$ for each $n$ and one can recover $w$ from $L(w)$. Thus there are uncountable many languages of the form $L(w)$. Since it has one word of each length, its generating function is $$1+x+x^2+\cdots = \dfrac{1}{1-x}.$$
Added to address the OP's comment below
There are trivially sequences $w\in \lbrace 0,1\rbrace^{\omega}$ whose language $L(w)$ is r.e. but not recursive. Namely, we can view $w$ as the characteristic function of a set $A$ of natural numbers. Clearly membership in $L(w)$ is the same as determining membership in $A$ as far as decidability goes, although there is perhaps some complexity blowup since to check if a string of length $n$ belongs to $L(w)$ we must check which of the first $n$ natural numbers belong to $A$ and conversely to check if an integer $n$ is in $A$, we have to look potentially at all bit strings of length $n. So this seems like a PSPACE blowup.
