Em alguns micros do meu trabalho esse problema também está ocorrendo. Acho que foi alguma atualização da Microsoft que gerou esse problema. Se você copiar o executável do Paint ( mspaint.exe ) de "system32" para "c:\Windows" e lá no "menu iniciar-programas-acessórios" configurar o atalho para o novo endereço ( c:\Windows\mspaint.exe ) abre normalmente. É assim que estamos fazendo aqui!
Aqui na empresa tambem começou a "pipocar" estaçoes assim... estamos copiando o mspaint.exe pro C:\ e mudando o atalho do paint em "all users".