If you import a frozen package (e.g. __phello__), __path__ is set to '__phello__'. But this should be a list as specified by both PEP 302 (http://www.python.org/dev/peps/pep-0302/) and the original doc outlining the package mechanism (http://www.python.org/doc/essays/packages.html). Changing import to put the string in a list is all that is needed to correct this (although it might break some code relying on the fact that it has been a string in previous versions).
Looking at Python/import.c:find_module, fixing this will require changing the setting of __path__ for frozen packages and how frozen modules are found. The former will require changing PyImport_ImportFrozenModule() to use a list instead of a string for the packages. To make the change work for find frozen modules, find_module() will need to change. Basically the special-casing for 'path' around frozen module just needs to go. This will lead to a slight performance penalty as all imports will require checking for an equivalent frozen module, but since it is a strcmp in a loop it should not be too bad. The performance cost can go away if some strapping young lad happens to re-implement import in such a way that the frozen module parts can easily be left out. =) Setting as a release blocker for now in case Barry is willing to let this go into 3.0rc4.
I have an attached patch that fixes the reported problem. First, it adds a sanity check that no empty module name is checked for (crashes the interpreter otherwise). Second, the __path__ attribute is now a list. This does break backwards-compatibility and thus cannot be backported to 2.6. Third, I removed the special-casing of frozen packages and just made frozen module checks a universal thing. This did change the module resolution order such that frozen modules are checked before built-in modules and registered modules under Windows (whatever those are). Moving frozen modules after those two cases are possible if it's really desired. At this point I need a review to get this into 3.0 and a decision on whether to backport to 2.7 (I say don't bother, out of backward-compatibility, but it probably wouldn't really hurt anything either).
