Things I would try:
- Make the gtk modules/libraries that you need included explicitly specified in the opts dict (both python modules and dlls).
- Make sure your py2exe included the gtk compiled libraries (dlls) like _gtk.dll ( 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, which is why the normal search path may not be working.