@Julien
I have been calling Python from C# without any problems even in a multi-threaded setup.  I am using .Net 2.0 and Python 2.5.  Main difference, at least from what I don't see in your code, is I also call BeginAllowThreads() after Initialize().  This allows me to initialize PythonEngine in a different thread once and never have to worry about it again.

I remember having similar problem when I first embedded Python and this doc helped me come up with this solution.
http://docs.python.org/c-api/init.html#thread-state-and-the-global-interpreter-lock

BTW, AcquireLock() below always returns 1.

Please let me know if this helps.

/* This is in main thread */
if (!PythonEngine.IsInitialized) {
    PythonEngine.Initialize();
    PythonEngine.BeginAllowThreads();
}
            
/* This is ran in another thread */
IntPtr gs = PythonEngine.AcquireLock();            

PyObject module = PythonEngine.ImportModule(pymodule);
try {
    PyObject res = module.InvokeMethod(method_name, _args);
    /* Python calls here */
   ....
} catch (PythonException pe) {
    /* Handle python exceptions */
} finally {
    PythonEngine.ReleaseLock(gs);
}