@J_Sparrow pues no sé porqué el mensaje de error no lo muestra correctamente.
En la última versión disponible, con la modificación de arriba tampoco muestra el mensaje traducido (foro en inglés) 
Si los cambios que te indica @andares te muestra el mensaje correctamente, lo demás puede adaptarse.
Para el asterisco, puedes añadirlo en la plantilla, aunque como lo usa en distintos lugares, se mostrará en el PCU también. Se podría "corregir" pero es mejor no modificar mucho para cuando actualices.
Archivo: ext/rmcgirr83/genders/styles/prosilver/template/ucp_user_gender.html
Busca: {L_GENDER}{L_COLON}
Remplaza con: {L_GENDER}{L_COLON} *