El método que te han explicado arriba es correcto: tienes que seleccionar como color primario el color a borrar y seleccionar como secundario el color al que quieres transformar para luego borrar el color deseado con el botón secundario del ratón.
Así que, o algo estás haciendo mal, o algo malo está pasando con el propio programa. Lo digo porque hay un bug en las versiones de MS Paint posteriores a la de Windows Vista (uno entre tantos que hay) que a veces te impide trabajar correctamente con el modo de borrar color. A veces por alguna razón no te deja borrar el color en píxeles que has pegado del portapapeles o en píxeles que hayas trazado con la herramienta de línea o de elipse. ¿Solución? Cortar y pegar la imagen, y luego volver a intentarlo:
Si no quieres que te vuelva a pasar, puedes bajarte una versión antigua de MS Paint (pre-Windows 7 y posterior al de Windows 3.1 cuando se llamaba Paintbrush) que tiene muchos menos bugs que el Paint actual, copiando el programa de alguna versión antigua de Windows que tengas instalada en alguna máquina, o bien descargándolo con ayuda de tu buscador de internet favorito.