Downgrading from libgcrypt-1.4.2-1 to libgcrypt-1.4.0-3 makes this problem go away.

Perhaps this indicates that there is a bug in libgcrypt-1.4.2-1, or perhaps this indicates that there is a bug in vino which doesn't manifest itself with the older libgcrypt version because the older version is less strict.  I leave this to the vino maintainer to figure out ;-).

I'm also encountering this problem. Haven't tried downgrading yet, but I've managed to get a backtrace which may be interesting for the package maintainer:

15/09/2008 21:24:58 Autoprobing TCP port 
15/09/2008 21:24:58 Autoprobing selected port 5900
15/09/2008 21:24:58 Advertising authentication type: 'VNC Authentication' (2)
15/09/2008 21:24:58 Advertising security type: 'VNC Authentication' (2)
15/09/2008 21:28:04 Got connection from client xxxxxxxxxxxx
15/09/2008 21:28:04   other clients:
15/09/2008 21:28:04 Client Protocol Version 3.7
15/09/2008 21:28:04 Advertising security type 2
15/09/2008 21:28:04 Client returned security type 2
fatal error in libgcrypt, file visibility.c, line 1197, function gcry_randomize: called in non-operational state

Program received signal SIGABRT, Aborted.
0x00110416 in __kernel_vsyscall ()
Missing separate debuginfos, use: debuginfo-install e2fsprogs.i386 expat.i386 gtk-nodoka-engine.i386 keyutils.i386 krb5.i386 libXau.i386 libXcomposite.i386 libXcursor.i386 libXdmcp.i386 libXi.i386 libXinerama.i386 libXrandr.i386 libXrender.i386 libcap.i386 libpng.i386 libselinux.i386 libxcb.i386 openssl.i686 pixman.i386
(gdb) bt
#0  0x00110416 in __kernel_vsyscall ()
#1  0x001c2740 in raise (sig=<value optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#2  0x001c4108 in abort () at abort.c:88
#3  0x04c29773 in _gcry_fips_noreturn () at fips.c:679
#4  0x04c21c42 in gcry_randomize (buffer=Could not find the frame base for "gcry_randomize".
) at visibility.c:1198
#5  0x0806448d in vncRandomBytes (bytes=0x80f0ae5 "") at vncauth.c:48
#6  0x08058b73 in rfbAuthProcessSecurityTypeMessage (cl=0x80f0ab8) at auth.c:275
#7  0x0805e2f8 in rfbProcessClientMessage (cl=0x80f0ab8) at rfbserver.c:370
#8  0x08053db8 in vino_server_client_data_pending (source=0x80d2dc0, condition=G_IO_IN, rfb_client=0x80f0ab8) at vino-server.c:334
#9  0x004091cd in g_io_unix_dispatch (source=<value optimized out>, callback=<value optimized out>, user_data=Could not find the frame base for "g_io_unix_dispatch".
) at giounix.c:162
#10 0x003d21f8 in g_main_dispatch () at gmain.c:2142
#11 IA__g_main_context_dispatch (context=<value optimized out>) at gmain.c:2694
#12 0x003d58a3 in g_main_context_iterate (context=<value optimized out>, block=<value optimized out>, dispatch=<value optimized out>, self=Could not find the frame base for "g_main_context_iterate".
) at gmain.c:2775
#13 0x003d5dc2 in IA__g_main_loop_run (loop=<value optimized out>) at gmain.c:2983
#14 0x04953fd9 in IA__gtk_main () at gtkmain.c:1172
#15 0x080512a0 in main (argc=Cannot access memory at address 0x5aa4
) at vino-main.c:110

I see we have libgrypt 1.4.3 in rawhide now. 
Does this still happen ?

The problem is gone as of libgcrypt 1.4.3-1