Попробуй добавить свой билдер: Tools > Build System > New Build System.
{
"shell_cmd": "python -u \"$file\"",
"file_regex": "^[ ]*File \"(...*?)\", line ([0-9]*)",
"selector": "source.python",
"encoding": "cp1251"
}
Это копия стандартного, плюс параметр: "encoding": "cp1251". Не забудь переключить на новый билдер: Tools > Build System > ...