I don't understand how the code you've shown can possibly be failing for you. Trying to reproduce your problem, I built the following pared-to-the-bone project:
$ ls -lR
total 32
-rw-r--r-- 1 aleax staff 0 Jun 10 21:20 __init__.py
drwxr-xr-x 4 aleax staff 136 Jun 10 21:28 a
-rw-r-----@ 1 aleax staff 107 Jun 10 21:27 app.yaml
-rw-r--r-- 1 aleax staff 21 Jun 10 21:20 cc.py
-rw-r--r-- 1 aleax staff 471 Jun 10 21:25 index.yaml
-rw-r--r-- 1 aleax staff 75 Jun 10 21:20 main.py
./a:
total 8
-rw-r--r-- 1 aleax staff 0 Jun 10 21:20 __init__.py
-rw-r--r-- 1 aleax staff 130 Jun 10 21:20 aa.py
Here are the nonempty Python files:
$ for f in main.py cc.py a/aa.py; do echo "File: $f"; cat $f; echo; done
File: main.py
print 'Content-Type: text/plain'
print ''
print 'in main'
from a import aa
File: cc.py
print 'in cc'
c = 23
File: a/aa.py
import os, sys
dirname=os.path.dirname
path=os.path.join(dirname(dirname(__file__)))
sys.path.insert(0,path)
import cc
print cc.c
$
It runs just fine, as predicted, showing (both when run locally on the SDK and when run on google's servers at appspot.com):
in main
in cc
23
So there must be some other error in parts of your code that you're not showing us. Please confirm this by reproducing this tiny project and trying it both locally and on appspot.com and let us know how it works (or fails...?) for you.