Got another one after restarting: in the middle of the second "song".

Looks similar to me:

[tbl@localhost ~]$ gdb rhythmbox
GNU gdb Fedora (6.8-12.fc10)
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 "i386-redhat-linux-gnu"...
(gdb) 
(gdb) run
Starting program: /usr/bin/rhythmbox 
[Thread debugging using libthread_db enabled]
[New Thread 0xb7f7c730 (LWP 22829)]
Detaching after fork from child process 22857.
[New Thread 0xb690cb90 (LWP 22859)]
[Thread 0xb690cb90 (LWP 22859) exited]
[New Thread 0xb690cb90 (LWP 22865)]
Detaching after fork from child process 22866.
[New Thread 0xb59ffb90 (LWP 22867)]
[Thread 0xb690cb90 (LWP 22865) exited]
[New Thread 0xb690cb90 (LWP 22868)]
[New Thread 0xb4dffb90 (LWP 22869)]
[New Thread 0xb43feb90 (LWP 22870)]
[Thread 0xb690cb90 (LWP 22868) exited]
[Thread 0xb43feb90 (LWP 22870) exited]
Detaching after fork from child process 22871.
Missing separate debuginfo for /home/tbl/.gstreamer-0.10/plugins/libgstflump3dec.so
[New Thread 0xb43feb90 (LWP 22890)]
[New Thread 0xb690cb90 (LWP 22891)]
[New Thread 0x25a1b90 (LWP 22892)]
[New Thread 0x35feb90 (LWP 22893)]
[New Thread 0x5ec6b90 (LWP 22894)]
[Thread 0x5ec6b90 (LWP 22894) exited]
[New Thread 0x5ec6b90 (LWP 22895)]
[New Thread 0x9033b90 (LWP 22896)]
[Thread 0x9033b90 (LWP 22896) exited]
[New Thread 0x9033b90 (LWP 22940)]
[New Thread 0x9f6db90 (LWP 22941)]
[Thread 0x9033b90 (LWP 22940) exited]
[Thread 0x9f6db90 (LWP 22941) exited]
[New Thread 0x9f6db90 (LWP 22995)]
[Thread 0x9f6db90 (LWP 22995) exited]
[New Thread 0x9f6db90 (LWP 23051)]
[New Thread 0x9033b90 (LWP 23052)]
[Thread 0x9f6db90 (LWP 23051) exited]
[Thread 0x9033b90 (LWP 23052) exited]
[Thread 0x5ec6b90 (LWP 22895) exited]
[New Thread 0x5ec6b90 (LWP 23064)]
[New Thread 0x9033b90 (LWP 23065)]
[New Thread 0x9f6db90 (LWP 23066)]
[Thread 0xb43feb90 (LWP 22890) exited]
[Thread 0x9f6db90 (LWP 23066) exited]
[New Thread 0x9f6db90 (LWP 23108)]
[New Thread 0xb43feb90 (LWP 23109)]
[Thread 0x9f6db90 (LWP 23108) exited]
[Thread 0xb43feb90 (LWP 23109) exited]

Program received signal SIGSEGV, Segmentation fault.
_int_malloc (av=<value optimized out>, bytes=<value optimized out>)
    at malloc.c:4126
4126	      if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
(gdb) print idx
$1 = <value optimized out>
(gdb) print chunksize
No symbol "chunksize" in current context.
(gdb) where
#0  _int_malloc (av=<value optimized out>, bytes=<value optimized out>)
    at malloc.c:4126
#1  0x008043e5 in __libc_malloc (bytes=<value optimized out>) at malloc.c:3551
#2  0x004fc354 in IA__g_malloc (n_bytes=<value optimized out>) at gmem.c:131
#3  0x07b8977c in gst_iterator_new (size=<value optimized out>, 
    type=<value optimized out>, lock=Could not find the frame base for
"gst_iterator_new".
) at gstiterator.c:129
#4  0x07b89883 in gst_iterator_filter (it=<value optimized out>, 
    func=<value optimized out>, user_data=Could not find the frame base for
"gst_iterator_filter".
) at gstiterator.c:449
#5  0x07b64266 in gst_bin_iterate_sinks (bin=<value optimized out>)
    at gstbin.c:1461
#6  0x07b67791 in gst_bin_query (element=<value optimized out>, 
    query=<value optimized out>) at gstbin.c:3156
#7  0x07b793b5 in gst_element_query (element=<value optimized out>, 
    query=<value optimized out>) at gstelement.c:1528
#8  0x07b6816e in bin_query_position_fold (item=<value optimized out>, 
    ret=<value optimized out>, fold=<value optimized out>) at gstbin.c:2989
#9  0x07b89477 in gst_iterator_fold (it=<value optimized out>, 
    func=<value optimized out>, ret=<value optimized out>, 
    user_data=<value optimized out>) at gstiterator.c:502
#10 0x07b6782d in gst_bin_query (element=<value optimized out>, 
    query=<value optimized out>) at gstbin.c:3166
#11 0x07b793b5 in gst_element_query (element=<value optimized out>, 
    query=<value optimized out>) at gstelement.c:1528
---Type <return> to continue, or q <return> to quit---
#12 0x07bb858a in gst_element_query_position (element=<value optimized out>, 
    format=<value optimized out>, cur=Could not find the frame base for
"gst_element_query_position".
) at gstutils.c:1911
#13 0x051575b0 in rb_player_gst_get_time (player=<value optimized out>)
    at rb-player-gst.c:1147
#14 0x051554f3 in rb_player_get_time (player=Could not find the frame base for
"rb_player_get_time".
) at rb-player.c:423
#15 0x05157ed0 in tick_timeout (mp=<value optimized out>)
    at rb-player-gst.c:218
#16 0x004f4796 in g_timeout_dispatch (source=Could not find the frame base for
"g_timeout_dispatch".
) at gmain.c:3522
#17 0x004f4081 in IA__g_main_context_dispatch (context=<value optimized out>)
    at gmain.c:2063
#18 0x004f75db 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:2696
#19 0x004f7aaa in IA__g_main_loop_run (loop=<value optimized out>)
    at gmain.c:2919
#20 0x04b23ac6 in IA__gtk_main () at gtkmain.c:1169
#21 0x0806018d in main (argc=1, argv=0x0) at main.c:340
(gdb) quit
The program is running.  Exit anyway? (y or n) y
[tbl@localhost ~]$ 

Crashes in malloc means that there's some invalid memory accesses. Try running
rhythmbox under valgrind.

Created attachment 310363 [details]
Valgrind ouput showing rhythmbox SIGSEGV crash

Here it is.

The last few lines are below.  Complete output attached.

==23957== Thread 1:
==23957== Invalid free() / delete / delete[]
==23957==    at 0x400590A: free (vg_replace_malloc.c:323)
==23957==    by 0x4FC1F5: g_free (gmem.c:190)
==23957==    by 0x4E3F48: g_error_free (gerror.c:125)
==23957==    by 0x69F789A: rb_audiocd_is_volume_audiocd
(rb-audiocd-source.c:739)
==23957==    by 0x69F6EB6: create_source_cb (rb-audiocd-plugin.c:449)
==23957==    by 0x516FFD5: rb_marshal_OBJECT__OBJECT (rb-marshal.c:327)
==23957==    by 0xCCE152: g_closure_invoke (gclosure.c:490)
==23957==    by 0xCE4F04: signal_emit_unlocked_R (gsignal.c:2510)
==23957==    by 0xCE5DC6: g_signal_emit_valist (gsignal.c:2209)
==23957==    by 0xCE63C5: g_signal_emit (gsignal.c:2243)
==23957==    by 0x807C2EC: rb_removable_media_manager_mount_volume
(rb-removable-media-manager.c:438)
==23957==    by 0x807C4CE: rb_removable_media_manager_scan
(rb-removable-media-manager.c:610)
==23957==  Address 0xb6aa310 is 0 bytes inside a block of size 65 free'd
==23957==    at 0x400590A: free (vg_replace_malloc.c:323)
==23957==    by 0x4FC1F5: g_free (gmem.c:190)
==23957==    by 0x4E3F48: g_error_free (gerror.c:125)
==23957==    by 0x303C9F: cd_cache_open_mountpoint (totem-disc.c:458)
==23957==    by 0x303D58: cd_cache_disc_is_vcd (totem-disc.c:645)
==23957==    by 0x303FFF: totem_cd_detect_type_with_url (totem-disc.c:861)
==23957==    by 0x3042CB: totem_cd_detect_type (totem-disc.c:936)
==23957==    by 0x69F7845: rb_audiocd_is_volume_audiocd
(rb-audiocd-source.c:735)
==23957==    by 0x69F6EB6: create_source_cb (rb-audiocd-plugin.c:449)
==23957==    by 0x516FFD5: rb_marshal_OBJECT__OBJECT (rb-marshal.c:327)
==23957==    by 0xCCE152: g_closure_invoke (gclosure.c:490)
==23957==    by 0xCE4F04: signal_emit_unlocked_R (gsignal.c:2510)
==23957== 
==23957== Thread 6:
==23957== Invalid read of size 4
==23957==    at 0x512CEB: g_slice_alloc (gslice.c:474)
==23957==    by 0x4F1E25: g_list_append (glist.c:122)
==23957==    by 0x505BCF: g_queue_push_tail (gqueue.c:368)
==23957==    by 0x6B88D48: gst_queue_locked_enqueue (gstqueue.c:663)
==23957==    by 0x6B8A6E4: gst_queue_chain (gstqueue.c:941)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x6B691A7: gst_selector_pad_chain (gststreamselector.c:422)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x7B83DE9: gst_proxy_pad_do_chain (gstghostpad.c:193)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==  Address 0x1 is not stack'd, malloc'd or (recently) free'd
==23957== 
==23957== Process terminating with default action of signal 11 (SIGSEGV)
==23957==  Access not within mapped region at address 0x1
==23957==    at 0x512CEB: g_slice_alloc (gslice.c:474)
==23957==    by 0x4F1E25: g_list_append (glist.c:122)
==23957==    by 0x505BCF: g_queue_push_tail (gqueue.c:368)
==23957==    by 0x6B88D48: gst_queue_locked_enqueue (gstqueue.c:663)
==23957==    by 0x6B8A6E4: gst_queue_chain (gstqueue.c:941)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x6B691A7: gst_selector_pad_chain (gststreamselector.c:422)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x7B83DE9: gst_proxy_pad_do_chain (gstghostpad.c:193)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957== 
==23957== ERROR SUMMARY: 9534 errors from 29 contexts (suppressed: 341 from 2)
==23957== malloc/free: in use at exit: 16,981,322 bytes in 97,409 blocks.
==23957== malloc/free: 691,088 allocs, 593,681 frees, 105,383,644 bytes
allocated.
==23957== For counts of detected errors, rerun with: -v
==23957== searching for pointers to 97,409 not-freed blocks.
==23957== checked 147,922,912 bytes.
==23957== 
==23957== LEAK SUMMARY:
==23957==    definitely lost: 59,742 bytes in 2,042 blocks.
==23957==      possibly lost: 803,217 bytes in 1,162 blocks.
==23957==    still reachable: 16,118,363 bytes in 94,205 blocks.
==23957==	  suppressed: 0 bytes in 0 blocks.
==23957== Rerun with --leak-check=full to see details of leaked memory.
Killed

Damn.  Attachments don't clear NEEDINFO.....

On the chance it had something to do with:

==23957== Source and destination overlap in memcpy(0xB7B79D4, 0xB7B7B14, 444)
==23957==    at 0x40076D9: memcpy (mc_replace_strmem.c:402)
==23957==    by 0xB91213F: ipp_decode_mp3 (in
/home/tbl/.gstreamer-0.10/plugins/libgstflump3dec.so)
==23957==    by 0xB90BBCF: mp3tl_decode_frame (in
/home/tbl/.gstreamer-0.10/plugins/libgstflump3dec.so)
==23957==    by 0xB903418: (within
/home/tbl/.gstreamer-0.10/plugins/libgstflump3dec.so)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x6C3AC8F: gst_tag_demux_chain (gsttagdemux.c:677)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==23957==    by 0x6B8E7E9: gst_type_find_element_chain (gsttypefindelement.c:613)
==23957==    by 0x7B91878: gst_pad_chain_unchecked (gstpad.c:3576)
==23957==    by 0x7B92A89: gst_pad_push (gstpad.c:3744)
==24092== 

I downloaded/installed newer version of the fluendo codec.

Will report if that has any effect.

Well, I'm not sure why, but it seems to be running "better": with the newer
version of fluendo library, I haven't been able to reproduce the SIGSEGV.

But then again, I'm not sure what caused this to start happening today either
(after a long long time of no problems).

Precisely, with the new library, I no longer see the above valgrind "destination
overalap in memcpy(....)" report in a run.

The only crashes I see now are due to:
E: time-smoother.c: Assertion 'x >= s->pause_time' failed at
pulsecore/time-smoother.c:421, function pa_smoother_resume(). Aborting.
(https://bugzilla.redhat.com/show_bug.cgi?id=447543)

That is reported to be fixed by new pulseaudio build in koji.

I'm really confused....... Are any of the other valgrind reported issues "real"?

At least one of them was. Fixed in trunk:
2008-06-27  Bastien Nocera  <hadess>

	* plparse/totem-disc.c (cd_cache_new), (cd_cache_open_mountpoint):
	When propagating errors, don't free the original error, spotted in
	https://bugzilla.redhat.com/show_bug.cgi?id=453020#c3

I'll close this as the other issue isn't our fault (it's in the Fluendo plugin).

Thanks