valgrind output shows that the immediate problem is that xrealloc in glx/glxscreen.c:276 causes some colormaps to have a bad pVisual member.. That is : some colormaps STILL point to the old memory .. In other words.. not all colormaps gets fixed up in AddScreenVisuals. Here is a gdb session where we track the colormaps created/destroyed.

adam@durum:~/xvfb$ gdb --args Xvfb  -auth hosts :1 
GNU gdb 6.8-debian
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 "x86_64-linux-gnu"...
(gdb) break colormap.c:279
Breakpoint 1 at 0x56db8c: file ../../dix/colormap.c, line 279.
(gdb) break FreeColormap
Breakpoint 2 at 0x56e2d1: file ../../dix/colormap.c, line 428.
(gdb) run
Starting program: /usr/bin/Xvfb -auth hosts :1
[Thread debugging using libthread_db enabled]
[New Thread 0x7f0639991710 (LWP 3767)]
[Switching to Thread 0x7f0639991710 (LWP 3767)]

Breakpoint 1, CreateColormap (mid=32, pScreen=0x2253800, pVisual=0x2253dc0, 
    ppcmap=0x7fff419bba90, alloc=0, client=0) at ../../dix/colormap.c:279
279	    if (!pmap)
(gdb) print pmap
$1 = (ColormapPtr) 0x2254e20
(gdb) bt
#0  CreateColormap (mid=32, pScreen=0x2253800, pVisual=0x2253dc0, 
    ppcmap=0x7fff419bba90, alloc=0, client=0) at ../../dix/colormap.c:279
#1  0x00000000005cf8b2 in miCreateDefColormap (pScreen=0x2253800)
    at ../../mi/micmap.c:318
#2  0x000000000056d551 in fbCreateDefColormap (pScreen=0x2253800)
    at ../../../fb/fbcmap_mi.c:91
#3  0x000000000042defc in vfbScreenInit (index=0, pScreen=0x2253800, argc=4, 
    argv=0x7fff419bbd28) at ../../../hw/vfb/InitOutput.c:952
#4  0x00000000005a1199 in AddScreen (pfnInit=0x42db2b <vfbScreenInit>, argc=4, 
    argv=0x7fff419bbd28) at ../../dix/main.c:702
#5  0x000000000042e0e3 in InitOutput (screenInfo=0x88a780, argc=4, 
    argv=0x7fff419bbd28) at ../../../hw/vfb/InitOutput.c:1018
#6  0x00000000005a03b6 in main (argc=4, argv=0x7fff419bbd28, 
    envp=0x7fff419bbd50) at ../../dix/main.c:315
(gdb) cont
Continuing.

Breakpoint 1, CreateColormap (mid=64, pScreen=0x2253800, pVisual=0x2253df8, 
    ppcmap=0x2254238, alloc=0, client=0) at ../../dix/colormap.c:279
279	    if (!pmap)
(gdb) print pmap
$2 = (ColormapPtr) 0x2265d90
(gdb) bt
#0  CreateColormap (mid=64, pScreen=0x2253800, pVisual=0x2253df8, 
    ppcmap=0x2254238, alloc=0, client=0) at ../../dix/colormap.c:279
#1  0x00000000004ee198 in PictureInitIndexedFormat (pScreen=0x2253800, 
    format=0x2254210) at ../../render/picture.c:417
#2  0x00000000004ee238 in PictureInitIndexedFormats (pScreen=0x2253800)
    at ../../render/picture.c:439
#3  0x00000000004ee28b in PictureFinishInit () at ../../render/picture.c:451
#4  0x00000000004f133c in RenderExtensionInit () at ../../render/render.c:244
#5  0x000000000042e41c in InitExtensions (argc=4, argv=0x7fff419bbd28)
    at ../../../mi/miinitext.c:457
#6  0x00000000005a03e1 in main (argc=4, argv=0x7fff419bbd28, 
    envp=0x7fff419bbd50) at ../../dix/main.c:319
(gdb) cont
Continuing.

Breakpoint 1, CreateColormap (mid=65, pScreen=0x2253800, pVisual=0x2253e30, 
    ppcmap=0x2254280, alloc=0, client=0) at ../../dix/colormap.c:279
279	    if (!pmap)
(gdb) print pmap
$3 = (ColormapPtr) 0x2271e50
(gdb) bt
#0  CreateColormap (mid=65, pScreen=0x2253800, pVisual=0x2253e30, 
    ppcmap=0x2254280, alloc=0, client=0) at ../../dix/colormap.c:279
#1  0x00000000004ee198 in PictureInitIndexedFormat (pScreen=0x2253800, 
    format=0x2254258) at ../../render/picture.c:417
#2  0x00000000004ee238 in PictureInitIndexedFormats (pScreen=0x2253800)
    at ../../render/picture.c:439
#3  0x00000000004ee28b in PictureFinishInit () at ../../render/picture.c:451
#4  0x00000000004f133c in RenderExtensionInit () at ../../render/render.c:244
#5  0x000000000042e41c in InitExtensions (argc=4, argv=0x7fff419bbd28)
    at ../../../mi/miinitext.c:457
#6  0x00000000005a03e1 in main (argc=4, argv=0x7fff419bbd28, 
    envp=0x7fff419bbd50) at ../../dix/main.c:319
(gdb) cont
Continuing.

Breakpoint 1, CreateColormap (mid=66, pScreen=0x2253800, pVisual=0x2253ed8, 
    ppcmap=0x2254310, alloc=0, client=0) at ../../dix/colormap.c:279
279	    if (!pmap)
(gdb) print pmap
$4 = (ColormapPtr) 0x227db00
(gdb) cont
Continuing.
[dix] Could not init font path element /usr/share/fonts/X11/cyrillic, removing from list!
(EE) config/hal: NewInputDeviceRequest failed (2)
(EE) config/hal: NewInputDeviceRequest failed (2)
(EE) config/hal: NewInputDeviceRequest failed (2)

Breakpoint 2, FreeColormap (value=0x2271e50, mid=65)
    at ../../dix/colormap.c:428
428	    ColormapPtr	pmap = (ColormapPtr)value;
(gdb) cont
Continuing.

Breakpoint 2, FreeColormap (value=0x2265d90, mid=64)
    at ../../dix/colormap.c:428
428	    ColormapPtr	pmap = (ColormapPtr)value;
(gdb) cont
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x000000000056e3d9 in FreeColormap (value=0x2265d90, mid=64)
    at ../../dix/colormap.c:454
454			if (--pent->co.shco.red->refcnt == 0)
(gdb) print *pmap
$5 = {pVisual = 0x2253df8, class = 1, pad0 = 0, pad1 = 0, mid = 64, pad2 = 0, 
  pScreen = 0x2253800, flags = 0, freeRed = 0, freeGreen = 0, freeBlue = 0, 
  numPixelsRed = 0x2268618, numPixelsGreen = 0x0, numPixelsBlue = 0x0, 
  clientPixelsRed = 0x2267e18, clientPixelsGreen = 0x0, 
  clientPixelsBlue = 0x0, red = 0x2265e18, green = 0x0, blue = 0x0, 
  devPriv = 0x0, devPrivates = 0x0}
(gdb) print *pmap->pVisual
$6 = {vid = 1919243129, class = 25974, bitsPerRGBValue = 21362, 
  ColormapEntries = 29300, nplanes = 28265, redMask = 33, 
  greenMask = 7307490906382814279, blueMask = 122485727655022, 
  offsetRed = 36273040, offsetGreen = 0, offsetBlue = 33}
(gdb) 

Clearly pmap->pVisual is wrong. It's the three colormaps created in PictureInitIndexedFormat that are missed in the AddScreenVisuals function. One colormap seems OK.. Namely the first one created in miCreateDefColormap .