i have a similar issue. Using windows 8, and the program opens, then immediately closes/crashes with a "has encountered a problem and needs to close" message.
i have tried uninstalling and reinstalling paint.net, and i cannot seem to find a previous version to try . i will search my backups for one.
From one of my crash logs, pdncrash.6
hope this helps. it only happened after updating to version 4.0