Hmm, I cannot reproduce, so more info is needed: 
  
First, please try to create a gdb backtrace.  Install the -debuginfo  
package for your gpa, install gdb if not already installed, and set "ulimit -c 
unlimited" in a shell before starting gpa, then run gpa, and finally gdb on 
the produced core dump file.  More info at 
http://fedoraproject.org/wiki/StackTraces  
  
Also, do you have a ~/.gnupg directory, and if you do, do you have any keys in 
your private/public GPG keyrings? 
 
Finally, unfortunately the status of gpa in Fedora Extras is that it's more or 
less unmaintained; I haven't even used it in a while.  
http://fedoraproject.org/wiki/Extras/OrphanedPackages 

It looks like it's caused by my (not so small) keyring. On a fresh user, it
doesn't happen.

Here the backtrace:

#0  0x00c5a402 in __kernel_vsyscall ()
(gdb) bt
#0  0x00c5a402 in __kernel_vsyscall ()
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x00566888 in *__GI_abort () at ../sysdeps/generic/abort.c:88
#3  0x0059a22a in __libc_message (do_abort=2, fmt=0x6571c0 "*** glibc detected
*** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:170
#4  0x005a019f in _int_free (av=0x663880, mem=0x9f06ed8) at malloc.c:5578
#5  0x005a065f in *__GI___libc_free (mem=0x9f06ed8) at malloc.c:3419
#6  0x009a7cc8 in gpgme_key_sig_get_ulong_attr () from /usr/lib/libgpgme.so.11
#7  0x009aed6f in gpgme_get_engine_info () from /usr/lib/libgpgme.so.11
#8  0x009aedc3 in gpgme_release () from /usr/lib/libgpgme.so.11
#9  0x08070762 in ?? ()
#10 0x0804feb7 in ?? ()
#11 0x00551d5f in __libc_start_main (main=0x804fb93, argc=1, ubp_av=0xbf9c7594,
init=0x80707cc, fini=0x807081c,
    rtld_fini=0x52d1ad <_dl_fini>, stack_end=0xbf9c758c) at
../sysdeps/generic/libc-start.c:216
#12 0x0804f831 in ?? ()

gpgme.i386                               1.0.3-1.2.fc4.rf

I've tried seahorse from dries, but this also crashes...also on new user.

(Cc'ing Rex, the Extras gpgme maintainer.) 
 
The backtrace is not too informative, but it looks like the crash   
happens in gpgme, not gpa.  I suggest you revert to the gpgme package from  
Fedora Extras (currently 1.0.2-3.fc4) and try again with it.  Seahorse is also  
available in Fedora Extras, if you want to give it a try.  
  
And in case you're not aware of it, I'd like to point out the possible  
pitfalls of mixing different repositories:  
http://fedoraproject.org/wiki/Extras/RepositoryMixingProblems 

Downgrading to gpgme-1.0.2-3.fc4 won't help, same issue (also on seahorse).

My pub keyring is about 2 M, will run tests with a smaller one next days.

Reassigning to gpgme due to what the backtrace shows, and that seahorse 
crashes too.  It'd be useful if you could install the -debuginfo package for 
gpgme, recreate the gdb backtrace, and post it here. 

FYI, just pushed gpgme-1.0.3-2 to fc3/fc4 to extras.  There's a (small) chance
this may help.

Waiting on confirmation whether gpgme-1.0.3 helps.

$ rpm -q gpgme
gpgme-1.0.3-2.fc4

Same issue, same backtrace:

#0  0x00c7d402 in __kernel_vsyscall ()
(gdb) bt
#0  0x00c7d402 in __kernel_vsyscall ()
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x00566888 in *__GI_abort () at ../sysdeps/generic/abort.c:88
#3  0x0059a22a in __libc_message (do_abort=2, fmt=0x6571c0 "*** glibc detected
*** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:170
#4  0x005a019f in _int_free (av=0x663880, mem=0x82beeb0) at malloc.c:5578
#5  0x005a065f in *__GI___libc_free (mem=0x82beeb0) at malloc.c:3419
#6  0x007af838 in gpgme_key_sig_get_ulong_attr () from /usr/lib/libgpgme.so.11
#7  0x007b8c9f in gpgme_get_engine_info () from /usr/lib/libgpgme.so.11
#8  0x007b8cf3 in gpgme_release () from /usr/lib/libgpgme.so.11
#9  0x08070762 in ?? ()
#10 0x0804feb7 in ?? ()
#11 0x00551d5f in __libc_start_main (main=0x804fb93, argc=1, ubp_av=0xbfe0fbf4,
init=0x80707cc,
    fini=0x807081c, rtld_fini=0x52d1ad <_dl_fini>, stack_end=0xbfe0fbec)
    at ../sysdeps/generic/libc-start.c:216
#12 0x0804f831 in ?? ()

I've tracked this now more and found hints for the reason:

1) the problem is caused by my secret keyring
2) if I delete *my* long used secret key from keyring  (it's the first in list),
gpa starts
3) gpa wrote gpa.conf with another default of my secret keys specified
4) if I use the original secret keyring, gpa starts, too
5) if I select the previous deleted secret key in gpa, it also starts afterwards
6) if I remove gpa.conf, it crashes on start

It looks like the problem is somewhere located after import secret keyring
during selection of the default secret key.

Note that this key contain following:

sec   1024D/958F422D 1997-10-30
uid                  Peter Bieringer <peter>
uid                  Peter Bieringer <pb>
uid                  [jpeg image of size 2660]
ssb   2048g/33068D31 1997-10-30

Damn, I was hoping that it would have been something in your public keyring so
it could have been sent somewhere for examination.  No such luck, it seems :(

But see comment 5, could you install the -debuginfo package for the gpgme you're
using and then regenerate the backtrace (see comment 5).  While at it, it might
not hurt to install pth-debuginfo as well.  The gpgme_*() calls in the backtrace
are missing line numbers and arguments which is a sign of a missing
gpgme-debuginfo.  "bt full" might also provide some more insight.

Just one more random hunch; is it possible for you to back up your keys and then
temporarily remove the jpeg image from the key that's causing the problems, and
try again?

gpgme-debuginfo was installed before, now I also installed pth-debuginfo.

I triggered 3 crashes now.

1) backtrace of original issue

(gdb) bt full
#0  0x00377402 in __kernel_vsyscall ()
No symbol table info available.
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
        resultvar = Variable "resultvar" is not available.
(gdb) bt
#0  0x00377402 in __kernel_vsyscall ()
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x00566888 in *__GI_abort () at ../sysdeps/generic/abort.c:88
#3  0x0059a22a in __libc_message (do_abort=2, fmt=0x6571c0 "*** glibc detected
*** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:170
#4  0x005a019f in _int_free (av=0x663880, mem=0x942cbe0) at malloc.c:5578
#5  0x005a065f in *__GI___libc_free (mem=0x942cbe0) at malloc.c:3419
#6  0x007af838 in release_op_data (hook=0x942bfb0) at keylist.c:67
#7  0x007b8c9f in _gpgme_release_result (ctx=0x942b9a0) at gpgme.c:137
#8  0x007b8cf3 in gpgme_release (ctx=0x942b9a0) at gpgme.c:116
#9  0x08070762 in ?? ()
#10 0x0804feb7 in ?? ()
#11 0x00551d5f in __libc_start_main (main=0x804fb93, argc=1, ubp_av=0xbfca27a4,
init=0x80707cc, fini=0x807081c,
    rtld_fini=0x52d1ad <_dl_fini>, stack_end=0xbfca279c) at
../sysdeps/generic/libc-start.c:216
#12 0x0804f831 in ?? ()


2) backtrace after looking into key after step 5 above (note that with
"selection" I only meant selecting for default

(gdb) bt full
#0  0x00c42402 in __kernel_vsyscall ()
No symbol table info available.
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
        resultvar = Variable "resultvar" is not available.
(gdb) bt
#0  0x00c42402 in __kernel_vsyscall ()
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x00566888 in *__GI_abort () at ../sysdeps/generic/abort.c:88
#3  0x0059a22a in __libc_message (do_abort=2, fmt=0x6571c0 "*** glibc detected
*** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:170
#4  0x005a0124 in _int_free (av=0x663880, mem=0x9bfd010) at malloc.c:5578
#5  0x005a065f in *__GI___libc_free (mem=0x9bfd010) at malloc.c:3419
#6  0x007af838 in release_op_data (hook=0x9bfb210) at keylist.c:67
#7  0x007b8c9f in _gpgme_release_result (ctx=0x9b17238) at gpgme.c:137
#8  0x007ac1cf in _gpgme_op_reset (ctx=0x9b17238, type=2) at op-support.c:72
#9  0x007afb52 in gpgme_op_keylist_start (ctx=0x9b17238, pattern=0x9bdacf0
"*********************...**",
    secret_only=0) at keylist.c:724
#10 0x08058849 in ?? ()
#11 0x009127e7 in g_cclosure_marshal_VOID__VOID () from /usr/lib/libgobject-2.0.so.0
#12 0x00907285 in g_closure_invoke () from /usr/lib/libgobject-2.0.so.0
#13 0x0091575b in g_signal_stop_emission () from /usr/lib/libgobject-2.0.so.0
#14 0x00916eb0 in g_signal_emit_valist () from /usr/lib/libgobject-2.0.so.0
#15 0x00917223 in g_signal_emit () from /usr/lib/libgobject-2.0.so.0
#16 0x07097028 in gtk_tree_selection_select_range () from
/usr/lib/libgtk-x11-2.0.so.0
#17 0x070a8c4e in gtk_tree_view_scroll_to_cell () from /usr/lib/libgtk-x11-2.0.so.0
#18 0x070b1329 in gtk_tree_view_set_model () from /usr/lib/libgtk-x11-2.0.so.0
#19 0x06fe6be2 in gtk_marshal_VOID__UINT_STRING () from /usr/lib/libgtk-x11-2.0.so.0
#20 0x00906d9b in g_cclosure_new_swap () from /usr/lib/libgobject-2.0.so.0


3) backtrace of another crash after removing all keys with photo, gpa crashes
after displaying message that old default key is missing and a new one needs to
be selected

(gdb) bt full
#0  0x009c2402 in __kernel_vsyscall ()
No symbol table info available.
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
        resultvar = Variable "resultvar" is not available.
(gdb) bt
#0  0x009c2402 in __kernel_vsyscall ()
#1  0x00565118 in *__GI_raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67
#2  0x00566888 in *__GI_abort () at ../sysdeps/generic/abort.c:88
#3  0x0059a22a in __libc_message (do_abort=2, fmt=0x6571c0 "*** glibc detected
*** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:170
#4  0x005a0124 in _int_free (av=0x663880, mem=0x832cb98) at malloc.c:5578
#5  0x005a065f in *__GI___libc_free (mem=0x832cb98) at malloc.c:3419
#6  0x007af838 in release_op_data (hook=0x83cfdd0) at keylist.c:67
#7  0x007b8c9f in _gpgme_release_result (ctx=0x83dae80) at gpgme.c:137
#8  0x007b8cf3 in gpgme_release (ctx=0x83dae80) at gpgme.c:116
#9  0x08070762 in ?? ()
#10 0x0804feb7 in ?? ()
#11 0x00551d5f in __libc_start_main (main=0x804fb93, argc=1, ubp_av=0xbfc84884,
init=0x80707cc, fini=0x807081c,
    rtld_fini=0x52d1ad <_dl_fini>, stack_end=0xbfc8487c) at
../sysdeps/generic/libc-start.c:216
#12 0x0804f831 in ?? ()

new gpgme-1.1.2-4/gpa-0.7.3-2 pushed to the repos.  Try it out.

Tried now, at least on FC5 it is working fine now with following versions:
 gpa-0.7.3-2.fc5
 gpgme-1.1.2-4.fc5

Have no FC4 system here anymore for testing this particular issue.

Good enough for me.  (: