To update, my problem might be related to trying to launch an exe from outside the ApplicationDirectory:
However, I put the exe into my Application Directory and changed the code to launch it from there, but it still doesn't work on Windows XP. I don't know if it will work on Windows Vista & 7.
A final update, I had to use workingDirectory on NativeProcessStartupInfo:
var info:NativeProcessStartupInfo = new NativeProcessStartupInfo();
info.executable = updateFile;
info.workingDirectory = File.applicationDirectory;
Not sure if this would allow it to run outside of applicationDirectory but this is good enough for me!