Sounds a bit odd, you shouldn't be able to use 'Open With' on executable files. You might want to invest in some antivirus software and do a scan, I know that Avira is free and decent (last I heard anyway).
Still, for your current issue you can try this:
Click <code>Start->Run</code> (or press the <code>Win</code> key and <code>R</code>)
Type <code>cmd</code> (then press enter)
The command line window should now be open
Type <code>assoc .exe=exefile</code> (then press enter)
Executable files should now behave normally again.
If that doesn't work then I'm not sure how you'd fix it without physically being there to take a look.