Things I would try:
- Make the gtk modules/libraries that you need included explicitly specified in the setup.py opts dict (both python modules and dlls).
- Make sure your py2exe included the gtk compiled libraries (dlls) like _gtk.dll (_gtk.so on *nix).

I did a quick check and IconTheme is actually an Object that gets created at runtime. It is not defined in gtk's __init__.py, which is why the normal search path may not be working.