I'm the Nokia guy responsible for the project.
It looks like PySide are huge (3x the size of PyQt and 6x the size of SMOKE-generated bindings!) and there is very little improvement they can do if they keep on using Boost::Python to generate PySide.
You're right: the current size of PySide is an issue, especially if you consider mobile environments such as Maemo, let alone the S60 platform. However, that's also why we are working on Shiboken, an alternate binding component which would create CPython extensions directly instead of using Boost.Python as an intermediate layer. Shiboken is still in its infancy, but we expect we'll be able to solve the size issues for once and all, while retaining full Python-level compatibility with the current bindings.
Unfortunately, there's not much info on this yet, but check our repo for the source code: qt.gitorius.org/pyside.