Here is the backtrace using gdb:

$ gdb python
GNU gdb (GDB) 7.6.1 (Debian 7.6.1-1)
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /usr/bin/python2.7...(no debugging symbols found)...done.
(gdb) set pagination 0  # avoids the need to press Enter to "scroll"
"on" or "off" expected.
(gdb) run pitivi # tell Python to launch the pitivi executable in the bin/ folderStarting program: /usr/bin/python pitivi # tell Python to launch the pitivi executable in the bin/ folder
warning: Could not load shared library symbols for linux-vdso.so.1.
Do you need "set solib-search-path" or "set sysroot"?
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
/usr/bin/python: can't open file 'pitivi': [Errno 2] No such file or directory
[Inferior 1 (process 28360) exited with code 02]

Hi Mathieu, please install the debug packages (python-dbg, gstreamer*-dbg, etc.) for all the pitivi dependencies as much as possible, and try "run /usr/bin/pitivi" at the gdb prompt (instead of "run pitivi"), because it seems python doesn't know the full path otherwise (as the errors above indicate)...

... and the magic happened!

Here is what I did: I installed first a few of the debug packages that you mentioned:

sudo aptitude install python-dbg gstreamer1.0-gnonlin-dbg gstreamer1.0-libav-dbg gstreamer1.0-plugins-bad-dbg gstreamer1.0-plugins-base-dbg gstreamer1.0-plugins-good-dbg gstreamer1.0-plugins-ugly-dbg

Then ran Pitivi from gdb using /usr/bin/pitivi... which opened Pitivi to my very surprise! I tried then just "run pitivi", which worked too... I then purged all the debug packages, just to see what happened... And still works!

Finally, I remembered that I had some upgrades since I reported the bug. Maybe the upgrade of python-gobject did it. Here is the report of the upgrade:

Start-Date: 2013-12-26  12:47:39
Upgrade: emacs-snapshot-common:amd64 (20131206-1, 20131226-1), at-spi2-core:amd64 (2.10.1-1, 2.10.2-1), python-gi-dev:amd64 (3.8.2-1, 3.10.2-1), gdebi-core:amd64 (0.9.1, 0.9.2), python-gobject:amd64 (3.8.2-1, 3.10.2-1), emacs-snapshot:amd64 (20131206-1, 20131226-1), python-gi:amd64 (3.8.2-1, 3.10.2-1), libatk-bridge2.0-0:amd64 (2.10.0-1+b1, 2.10.2-1), gdebi:amd64 (0.9.1, 0.9.2), gir1.2-atspi-2.0:amd64 (2.10.1-1, 2.10.2-1), libsdl-ttf2.0-0:amd64 (2.0.11-2, 2.0.11-3), openssh-client:amd64 (6.4p1-1, 6.4p1-2), python-gi-cairo:amd64 (3.8.2-1, 3.10.2-1), emacs-snapshot-bin-common:amd64 (20131206-1, 20131226-1), libatspi2.0-0:amd64 (2.10.1-1, 2.10.2-1), libatk-adaptor-data:amd64 (2.10.0-1, 2.10.2-1), python3-gi:amd64 (3.8.2-1, 3.10.2-1), libatk-bridge2.0-dev:amd64 (2.10.0-1+b1, 2.10.2-1), libatk-adaptor:amd64 (2.10.0-1+b1, 2.10.2-1), libsdl-net1.2:amd64 (1.2.8-3, 1.2.8-4)
Error: Sub-process /usr/bin/dpkg returned an error code (1)
End-Date: 2013-12-26  12:48:15

(the dpkg error is about emacs-snapshot)

Anyway, Pitivi is now working as expected, and I'm happy.

Alright, closing this bug report as no further information can be provided.
Please feel free to reopen this bug if you can reproduce and provide that info.
Thanks!