I've made some progress on this issue. Thanks to Waldemar's findings, I'm able to selectively reproduce the issue by installing/uninstalling the Visual C++ redistributable that includes KB2467174 on a Windows 7 RTM installation.

So I added a patch to cpython to help troubleshoot:

    PS C:\Users\jaraco\projects\public\cpython\pcbuild> hg id
    434dfe42fde1+
    PS C:\Users\jaraco\projects\public\cpython\pcbuild> hg diff
    diff -r 434dfe42fde1 Python/import.c
    --- a/Python/import.c   Sun May 15 13:16:22 2011 +0200
    +++ b/Python/import.c   Mon May 16 10:52:45 2011 -0400
    @@ -1807,6 +1807,15 @@
         /* Check for package import (buf holds a directory name,
            and there's an __init__ module in that directory */
     #ifdef HAVE_STAT
    +    if (Py_VerboseFlag > 1 && _Py_stat(filename, &statbuf) == 0) {
    +        PySys_FormatStderr("stat_mode %U: %d\n",
    +                           filename, statbuf.st_mode);
    +    }
    +    else if(Py_VerboseFlag > 1)
    +    {
    +        PySys_FormatStderr("_Py_stat(%U) returned %d\n",
    +            filename, _Py_stat(filename, &statbuf));
    +    }
         if (_Py_stat(filename, &statbuf) == 0 &&         /* it exists */
             S_ISDIR(statbuf.st_mode))           /* it's a directory */
         {


I then ran the test script without vcredist:

    C:\Users\Jason R. Coombs\Desktop>u:\users\jaraco\projects\public\cpython\pcbuild\amd64\python -vv .\test_import_symlink_package.py   2>&1  | findstr sample
    stat_mode .\sample: 16895
    import sample # directory '.\\sample'
    _Py_stat(.\sample\__init__) returned -1
    # trying '.\\sample\\__init__.pyd'
    # trying '.\\sample\\__init__.py'
    import sample # from '.\\sample\\__init__.py'
    # wrote '.\\sample\\__pycache__\\__init__.cpython-32.pyc'
    # cleanup[1] sample

And again with the vcredist installed:

    C:\Users\Jason R. Coombs\Desktop>u:\users\jaraco\projects\public\cpython\pcbuild\amd64\python -vv .\test_import_symlink_package.py   2>&1  | findstr sample
    _Py_stat(.\sample) returned -1
    # trying '.\\sample.pyd'
    # trying '.\\sample.py'
    # trying '.\\sample.pyw'
    # trying '.\\sample.pyc'
    No module named 'sample'

Basically, it appears that with the later vcredist installed, _Py_stat is returning -1 for symlink directories.