More information, and another piece of the puzzle:

I began tearing apart the headers of the libgcc3_uno.so built on karmic, and jaunty, and noticed an interesting anomaly with the program headers between the jaunty and karmic/lucid versions of this library, the karmic version doesn't have an .eh_frame_hdr

readelf output on jaunty:
mcasadevall@dawn:/usr/lib/ure/lib$ readelf -l libgcc3_uno.so.jaunty

Elf file type is DYN (Shared object file)
Entry point 0x22a0
There are 8 program headers, starting at offset 52

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x010534 0x00010534 0x00010534 0x00a60 0x00a60 R   0x4
  LOAD           0x000000 0x00000000 0x00000000 0x10fd4 0x10fd4 R E 0x8000
  LOAD           0x011e98 0x00019e98 0x00019e98 0x003a8 0x003d8 RW  0x8000
  DYNAMIC        0x011ed8 0x00019ed8 0x00019ed8 0x00128 0x00128 RW  0x4
  NOTE           0x000134 0x00000134 0x00000134 0x00024 0x00024 R   0x4
  GNU_EH_FRAME   0x010f94 0x00010f94 0x00010f94 0x00014 0x00014 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4
  GNU_RELRO      0x011e98 0x00019e98 0x00019e98 0x00168 0x00168 R   0x1

 Section to Segment mapping:
  Segment Sections...
   00     .ARM.exidx 
   01     .note.gnu.build-id .hash .dynsym .dynstr .gnu.version .gnu.version_d .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .ARM.extab .ARM.exidx .eh_frame_hdr .eh_frame 
   02     .init_array .fini_array .jcr .data.rel.ro .dynamic .got .data .bss 
   03     .dynamic 
   04     .note.gnu.build-id 
   05     .eh_frame_hdr 
   06     
   07     .init_array .fini_array .jcr .data.rel.ro .dynamic 

readelf output on karmic version:
mcasadevall@dawn:/usr/lib/ure/lib$ readelf -l libgcc3_uno.so.karmic

Elf file type is DYN (Shared object file)
Entry point 0x2550
There are 7 program headers, starting at offset 52

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  EXIDX          0x00bb7c 0x0000bb7c 0x0000bb7c 0x00748 0x00748 R   0x4
  LOAD           0x000000 0x00000000 0x00000000 0x0c2c8 0x0c2c8 R E 0x8000
  LOAD           0x00ce88 0x00014e88 0x00014e88 0x003bc 0x003ec RW  0x8000
  DYNAMIC        0x00cec8 0x00014ec8 0x00014ec8 0x00138 0x00138 RW  0x4
  NOTE           0x000114 0x00000114 0x00000114 0x00024 0x00024 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4
  GNU_RELRO      0x00ce88 0x00014e88 0x00014e88 0x00178 0x00178 R   0x1

 Section to Segment mapping:
  Segment Sections...
   00     .ARM.exidx 
   01     .note.gnu.build-id .hash .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_d .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .ARM.extab .ARM.exidx .eh_frame 
   02     .init_array .fini_array .jcr .data.rel.ro .dynamic .got .data .bss 
   03     .dynamic 
   04     .note.gnu.build-id 
   05     
   06     .init_array .fini_array .jcr .data.rel.ro .dynamic 

eh_frame and eh_frame are parts of the ELF file that deal with exception handling, which seems to be related to our issues with the unwinder failures. I managed to force inclusion of .eh_frame_hdr in a karmic build, but it didn't produce a working libgcc3_uno.so; seems to me that we may be getting corrupted eh_frame info, and I suspect not having .eh_frame_hdr automatically added is playing a part of this.