I confirm that problem with deadlock on execution of PyImport_ImportModuleLevel exists. Here is a working example:

1) Python was embbeded with C++ application using Python for scripting support:

------------------------------------------------------------------
PyThreadState * InitThreadScripting()
{
	ASSERT_KOBOLD( g_pyMainThreadState );

	// get the global lock
	PyEval_AcquireLock();
	// get a reference to the PyInterpreterState
	PyInterpreterState * mainInterpreterState = g_pyMainThreadState->interp;
	ASSERT_KOBOLD( mainInterpreterState );
	// create a thread state object for this thread
	PyThreadState * myThreadState = PyThreadState_New(mainInterpreterState);
	// free the lock
	PyEval_ReleaseLock();

	return myThreadState;
}

---------------------------------------------------------------------
void DeadLock()
{
Py_Initialize();
PyEval_InitThreads();
g_AiGlobals     = new Py::Dict();
g_pyInterpState = PyInterpreterState_New();

// save a pointer to the main PyThreadState object
g_pyMainThreadState = PyThreadState_Get();
ASSERT_KOBOLD( g_pyMainThreadState );

// release the lock
PyEval_ReleaseLock();

g_pyWorldThreadState = InitThreadScripting();

// import sys
// sys.path.append ("./scripts")
// 
PyObject	*p = PyImport_ImportModuleEx ("sys", **g_AiGlobals, NULL, NULL);
Py::Module	mod_sys (p);
Py::List	path = mod_sys.getAttr ("path");
path.append (Py::String ("scripts"));
path.append (Py::String ("scripts/sys"));
path.append (Py::String ("../../scripts"));
path.append (Py::String ("../../scripts/sys"));
Py_XDECREF (p);

// HERE IT OCCURS //
Log.ScriptsSrc("Python", "Running startup python scripts...");
PyObject *p = PyImport_ImportModuleEx ("startup", **g_AiGlobals, NULL, NULL); // <<< Here
if (reload) PyImport_ReloadModule (p);
Py::Module	module (p);
Py_XDECREF (p);
}

Execution locks right on PyImport_ImportModuleEx. 

Code from sturtup.py:
------------------------------------------------------------------------------------
# This module is sturtup script.
# Here we are redirecting output and checking for server version.
################################################################################

import sys
from consts import *   # Import of constants
import config as cfg   # Import of configuration constants
reload(cfg)  

################################################################################

# ----------------------------------------------------------------------------------------------------------------------------------------------------------------
class OurLogStdErr:
    def write (self, txt):
        printLog (txt, PRINT_ERROR)
        
# ----------------------------------------------------------------------------------------------------------------------------------------------------------------
class OurLogStdOut:
    def write (self, txt):
        printLog (txt)

# ----------------------------------------------------------------------------------------------------------------------------------------------------------------
def CheckServerVersion():
    # Checking for server build
    if GetServerBuild() < MIN_SERVER_BUILD:
        printLog( "YOU ARE TRYING TO RUN PYTHON SCRIPTS ON OUTDATED SERVER BUILD!\
\nREQUIRED SERVER BUILD: %s\
\nPlease Update your server core before running server!\
\nScripting Engine will be Shut Down!"\
        % (MIN_SERVER_BUILD), PRINT_ERROR )

        killScripting()
        
# ----------------------------------------------------------------------------------------------------------------------------------------------------------------
def GetScriptsVersion():
	return SCRIPTS_VERSION

################################################################################
# Startup code here:

# Redirecting errors:
sys.stderr = OurLogStdErr()

# Redirecting output:
sys.stdout = OurLogStdOut()

---------------------------------------------------------------------------------------