Not all encodings are included in the MonoTouch class library by default. To reduce the size of the application, MonoTouch doesn't include any specific encoding, and you have to instruct mtouch to include the assemblies containing the support for the encoding you need.
This is done using the -i18n switch, which takes a list of coma separated names, between:
So a command line would look like: mtouch -i18n=cjk,mideast ...
You can specify this from the IDE in the "iPhone Build" section in the Project Options, and you can add this to "Extra Arguments". Newer versions of MonoDevelop list the assemblies directly as "i18n Assemblies" in the iPhone Build section.
Here's the list of the supported code pages in each assembly.