After some poking around I settled on PySide which is the bindings for QT from Nokia. Its nice. Seems a little cleaner but actually pretty similar to wxPython in many ways.
At first I tried to use py2exe to make a single exe binary but I could never get this to work properly. The exe would always die somewhere during load and after spending too much time trying to sort that out I decided to use cx_freeze to much the same result. I also tried going back to Python 2.5 since that seems to have fewer MS DLL issues and PySide is available for that as well. Still no love.
Finally I tried Py-installer and it all pretty much worked right out of the box. Just go through the install step by step and you should be fine. Py-installer integrates with Upx and my final exe came in at around 6MB.
If you are stuck with having to deploy an app on windows, you don’t need anything more that python, pyside and pyinstaller. As a bonus the app will also run on your real computer.