The default pytz package is generally accepted to be unsuitable for GAE because of the load time. Rodrigo Moraes has created a version called gaepytz that is more suitable to GAE's distributed architecture.
I downloaded the zip version from the Python site thinking that I could use zipimport as described at this GAE article: http://code.google.com/appengine/articles/django10_zipimport.html
GAE complained about not being able to find my reference to gaepytz. A little tinkering around revealed that the only files necessary are the ones in the pytz folder and that either GAE or zipimport doesn't like hyphens in the zip. So I unzipped the gaepytz zip, then repackage it with:
zip -r gaepytz.zip pytz
With this, the error saying that it couldn't find the gaepytz file went away and was replaced with the following:
IOError: [Errno 20] Not a directory: '.../gaepytz.zip/pytz/zoneinfo.zip'
Turns out that zipimport doesn't like nested zip files. The next step was to unzip the gaepytz.zip file and just use the pytz folder directly. This meant going from 1 file at 512kB to 6 files at 569kB which isn't the end of the world.
The next bit was to dig into the comments of the source code to figure out how to use the package because import pytz clearly wasn't the answer. In the comments of one of the files is the helpful note:
import sys sys.path.insert(0, 'gaepytz') from pytz.gae import pytz
You only need the last line since the pytz folder is added directly and no longer in the zip file. A little more work than I was originally counting on, but glad to have it working.