Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?
It looks like Turing machines remain Turing-complete when the alphabet is restricted to have one symbol,&nbsp;$0$. First, preprocess your input by replacing every $0$ with $0\square$, where $\square$ is the blank symbol. Now, you can simulate a 2-symbol alphabet by using $0\square$ to represent zero and $\square0$ to represent one.


  My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers


This is incorrect. A language is, by definition, a set of finite strings and there are only countably many finite strings over any finite alphabet (proof: you get a bijection with the natural numbers by treating each string as a number written in base-$k$, where $k$ is the size of the alphabet). However, there are uncountably many different languages and that observation along with the countability of the set of Turing machines lets you deduce that there must be some undecidable langauges.


  It seems to me that, although you can encode any integer with the language 0∗, you can't encode an arbitrary language.


This is also incorrect. You can encode any natural number $n$ with the single string $0^n$ and, therefore, you can code any set of natural numbers with a unary language, i.e., a subset of $0^*$.  And you can code any set of natural numbers as a language. You can also code any language over an alphabet of size $k&gt;1$ by using the base-$k$ trick I described above.