maybe a stupid question/idea.
You wrote “after removing all applications” …
in the Setup / config admin login have you done this with the help of “Step 4 - advanced application management / Manage applications” because there is a checkbox called remove - this is not the right way.
For change the char set it is necessary to use “Step 1 - simple application management / Uninstall all applications” . After this step, you will be asked if you want to do a fresh install or restore a db backup, here it is possible to mark the char set change
BE SURE that you have made a backup before!