Uncle google is telling me to try wiping its registry tree, rebooting and trying again:

Delete:
HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Applets\Paint

Also it says MSPaint.exe is targeted by certain pieces of spyware. Perhaps the program is getting re-infected each time you run it, and an on-access virus prevention tool is shutting it down, thus the problem where it ran once and then never ran again. (It ran once uninfected, subsequent times it's getting shut down by the virus scanner.)