My guess is e_signature_new_from_xml() failed for some reason and returned NULL.  We of course don't check for NULL and just blindly dereference the pointer.

               211: signature = e_signature_new_from_xml (l->data);
               212: have_autogen |= signature->autogen;
      crash -> 213: if (!signature->uid) {
               214:         signature->uid = e_uid_new ();
               215:         resave = TRUE;
               216: }

Seb, could you ask for the content of /apps/evolution/mail/signatures
to try to reproduce on his/her data, please? Thanks in advance.

Matt, could be, though on 212 is also signature->, maybe it's off by one line.

On evolution-2.26.3-1.1mdv2009.1, I have the same errors. 
Clearing .evolution and gconf-editor give an empty signature: "[]"
Crash is:
gdb /usr/bin/evolution 
GNU gdb 6.8-6mdv2009.1 (Mandriva Linux release 2009.1)
Copyright (C) 2008 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 "i586-mandriva-linux-gnu"...
(gdb) r
Starting program: /usr/bin/evolution 
[Thread debugging using libthread_db enabled]
[New Thread 0xb64356e0 (LWP 12854)]

Program received signal SIGSEGV, Segmentation fault.
gconf_signatures_changed (client=0x9384aa8, cnxn_id=1191182347, entry=0x0, user_data=0x937d5b8)
    at e-signature-list.c:212
212				have_autogen |= signature->autogen;

If you add one entry it will work:
<?xml version="1.0"?><signature name="Autogenerated" uid="1119860287.6720.0@henry" auto="true" format="text/html"/>
but if you add a comma "," (meaning an empty second signature) it will crash probably for the reason raised above by Matthew Barnes.

On a very new installation of Linux and evolution, Evolution is crashing.

Created commit d24e00a in evo master (2.29.1+)
Created commit de1a7cd in evo gnome-2-28 (2.27.93+)

Thanks for the pointers. I was unable to reproduce with an empty list of signatures, thus it's possible your list seems empty, but contains one space or something "not visible", as with something like that I was able to reproduce it, on both 2.27 and master branches, even the code in both changed, thus it was crashing later. Nonetheless, with the above commits it doesn't crash any more, it ignores incorrect signatures and drops them on start/load.