Sorry to hear that. With the wxPython Project Phoenix shaping up, I'm removing support for v1 from pubsub: it complicates the package import significantly.
The source at
pubsub.sf.net will have this very shortly; if you'll plunk pubsubroot/src/pubsub in wx.lib and setup for arg1 messaging, it should work. I'm curious to see if your py2exe'd app has any issues then, it shouldn't. Note that AFAIK some have successfully py2exe'd their wxPython app but I don't have any details (version, etc).
Note that pubsub v3 uses the "kwargs" messaging protocol by default, but supports the "arg1" protocol which is likely to require only one line modification in your entire app. See the examples in source dist. Let me know if you have any problems.