es fácil:
MessageBoxA es más para python 2.7
ahora probá con MessageBoxW

Las funciones MessageBoxA y MessageBoxW son practicamente lo mismo, la diferencia es que la primera es la versión ANSI (A), y la segunda es la versión Unicode (W) (esto es así por norma general para cualquier función que tenga su adaptación ANSI plus Unicode, no solo con esta función),
el tratamiento de los caracteres de entrada y de retorno cambia (y eso ya debería daros una pista de donde está el problema real, ya que los strings unicodes de py2.7 cambiaron a py3.x), pero una función de Python no tiene por que funcionar en py2.X/py3.X mientras que la otra deja de funcionar, ya que particulármente esas funciones son un simple wrapper de las funciones de la API de Windows; por ende, ambas funciones deberían funcionar correctamente siempre que se esté utilizando la codificación adecuada en los parámetros que recibe la función, y ese es el fallo que aquí se está cometiendo, una manera de solucionarlo sería usando la función str.encode() para codificar el string usando el código de página apropiado para la cultura ANSI específica (CP1252):

# -*- coding: Windows-1252 -*-
 
import ctypes
ctypes.windll.user32.MessageBoxA(0, "Your text".encode('Windows-1252'), "Your title".encode('Windows-1252'), 0)

Saludos!

Elektro:
            sin lugar a dudas tu respuesta es más completa y correcta, pero... python 3.x viene con codificación unicode por defecto, por lo tanto es más fácil solo cambiar la A por W y no hay que aclarar la codificación, porque sino no los resultados de la función no son los mismos en 2.7 y 3.x