I've got the Microsoft Visual C++ 2008 SP1 Redistributable x64 and x86 and I also just installed the 2010 Runtime (both x64 and x86) and the 2005 SP1 Redistributable (again, x64 and x86) which have made no difference.
Event Viewer might have yielded some useful information, it generates 3 errors every time I attempt to run the executable.
---------------- Error 1 ----------------
Source: SideBySide
EventID: 32
Dependent Assembly Microsoft.Windows.Common-Controls could not be found and Last Error was The referenced assembly is not installed on your system.
---------------- Error 2 ----------------
Source: SideBySide
EventID: 59
Resolve Partial Assembly failed for Microsoft.Windows.Common-Controls. Reference error message: The referenced assembly is not installed on your system.
---------------- Error 3 ----------------
Source: SideBySide
EventID: 59
Generate Activation Context failed for C:\PathTo\MeGUI.exe. Reference error message: The referenced assembly is not installed on your system.
----------------------------------------
Edit: Possibly microsoft's fault
http://support.microsoft.com/kb/914061
Edit #2: No joy, that hotfix is apparently included in SP2
Edit #3: After looking at sxstrace logs it looks like Windows Server 2003 doesn't possess the required assembly code.