I have installed the default GNOME selection, autologged to a GNOME session and called "pstree -a". It segfaulted. Without -a it is fine. pstree -c 2626 is also fine.
It seems the bug is locale dependent:

linux:~ # LANG=C pstree -a 2626
nautilus --no-default-window --sm-client-id default2
  |-{nautilus}
  |-{nautilus}
  |-{nautilus}
  `-{nautilus}
linux:~ # LANG=C pstree -U -a 2626
nautilus --no-default-window --sm-client-id default2
  ├─{nautilus}
  ├─{nautilus}
  ├─{nautilus}
  └─{nautilus}
linux:~ # echo $LANG
cs_CZ.UTF-8
linux:~ # pstree -a 2626
nautilus --no-default-window --sm-client-id default2
  ├─{nautilus}
Neoprávněný přístup do paměti (SIGSEGV)
linux:~ # LANG=en_US.UTF-8 pstree -a 2626
nautilus --no-default-window --sm-client-id default2
  ├─{nautilus}
Neoprávněný přístup do paměti (SIGSEGV)
linux:~ # LANG=en_US.UTF-8 pstree -U -a 2626
nautilus --no-default-window --sm-client-id default2
  ├─{nautilus}
Neoprávněný přístup do paměti (SIGSEGV)


So here with a GDB trace:
linux:~ # gdb /usr/bin/pstree
GNU gdb 6.4
Copyright 2005 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i586-suse-linux"...(no debugging symbols found)
Using host libthread_db library "/lib/libthread_db.so.1".

(gdb) symbol-file /usr/lib/debug/usr/bin/pstree.debug
Reading symbols from /usr/lib/debug/usr/bin/pstree.debug...done.
(gdb) r -a 2626
Starting program: /usr/bin/pstree -a 2626
nautilus --no-default-window --sm-client-id default2
  ├─{nautilus}

Program received signal SIGSEGV, Segmentation fault.
0x08049971 in dump_tree (current=0x80522d0, level=1, rep=1, leaf=0, last=0, prev_uid=1000, closing=0) at pstree.c:484
484                 len += *here > ' ' && *here <= '~' ? 1 : 4;
(gdb) bt
#0  0x08049971 in dump_tree (current=0x80522d0, level=1, rep=1, leaf=0, last=0, prev_uid=1000, closing=0) at pstree.c:484
#1  0x08049d5b in dump_tree (current=0x8052288, level=0, rep=1, leaf=1, last=1, prev_uid=0, closing=0) at pstree.c:429
#2  0x0804a865 in main (argc=3, argv=0x0) at stdlib.h:336
(gdb) info locals
walk = <value optimized out>
next = <value optimized out>
scan = <value optimized out>
lvl = <value optimized out>
i = 0
add = 0
offset = 15
len = 0
info = <value optimized out>
count = <value optimized out>
comm_len = 10
first = <value optimized out>
here = 0xbfec0200 "�"\005\b\n"
comm_tmp = "\0008\002�

(BTW I don't understand why I have to explicitly say symbol-file. BTW^2, is valgrind not able to use debuginfo packages?)