This bug was reported to the Debian BTS.
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=389667

"This bug seems to happen relatively randomly, but I can create
circumstances that will pretty reliably cause it to happen. From what
I've read, this is probably a driver bug, but I don't know. This happens
with a game, UFO:AI, as well, consistently. If I start that (then
restart X), then start rhythmbox, it will hang on startup (everytime
I've tried). Generally it happens if I leave rhythmbox playing for an
extended period of time, or if I leave it paused for a short period of
time. I'm not sure how long it needs to be paused, but everytime I've
paused it, but the time I wanted to play again, it was hung. Which means
using muine or restarting. Muine and totem both work without hanging. As
far as debugging, I'm not sure where to start. Running rhythmbox through
gdb was fruitless (gdb also seemed to hang)."

and

"Running with --debug, didn't seem very fruitful to me.

The last messages I got:

(19:29:18) [0x814f8f8] [eos_cb] rb-shell-player.c:2387: eos!
(19:29:18) [0x814f8f8] [rb_random_play_order_get_next]
rb-play-order-random.c:333: choosing random entry
(19:29:18) [0x814f8f8] [rb_random_play_order_get_next]
rb-play-order-random.c:340: choosing enqueued entry
(19:29:18) [0x814f8f8] [rb_random_play_order_get_previous]
rb-play-order-random.c:386: choosing history entry
(19:29:18) [0x814f8f8] [rb_shell_player_open_location] rb-shell-player.c:984:
Opening file:///mnt/data/Sonata Arctica/09 - Sonata Arctica - Winterheart's
Guild - 2003/07 - Sonata Arctica - Champagne Bath.mp3...
(19:29:18) [0x814f8f8] [rb_player_gst_sync_pipeline] rb-player-gst.c:586:
syncing pipeline
(19:29:18) [0x814f8f8] [rb_player_gst_sync_pipeline] rb-player-gst.c:597:
PAUSING pipeline
(19:29:18) [0x814f8f8] [rb_player_gst_sync_pipeline] rb-player-gst.c:586:
syncing pipeline
(19:29:18) [0x814f8f8] [rb_player_gst_sync_pipeline] rb-player-gst.c:588:
PLAYING pipeline
(19:29:18) [0x814f8f8] [rb_shell_player_set_playing_entry]
rb-shell-player.c:1133:
Success!
(19:29:18) [0x814f8f8] [rb_tray_icon_notify] rb-tray-icon.c:526: doing
notify: Champagne Bath

(rhythmbox:3114): Rhythmbox-WARNING **: failed to send notification
(Champagne Bath)
(19:29:18) [0x814f8f8] [rb_shell_player_sync_with_source]
rb-shell-player.c:2048:
playing source: 0x8310068, active entry: 0x8543280
(19:29:18) [0x814f8f8] [rb_shell_set_window_title] rb-shell.c:2040: setting
title to "Sonata Arctica - Champagne Bath"
(19:29:18) [0x814f8f8] [rb_header_sync] rb-header.c:331: syncing with entry
= 0x8543280
(19:29:18) [0x814f8f8] [rb_shell_player_sync_buttons] rb-shell-player.c:2107:
syncing with source 0x8310068
(19:29:18) [0x814f8f8] [eos_cb] rb-shell-player.c:2447: updating play
statistics(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2541:
info: 0
(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2561: Got
info_available but entry isn't an iradio station
(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2541: info: 4
(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2561: Got
info_available but entry isn't an iradio station
(19:29:18) [0x814f8f8] [rb_shell_clipboard_entryview_changed_cb]
rb-shell-clipboard.c:694: entryview changed
(19:29:18) [0x814f8f8] [rb_shell_clipboard_sync] rb-shell-clipboard.c:486:
syncing clipboard
(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2541: info: 20
(19:29:18) [0x814f8f8] [info_available_cb] rb-shell-player.c:2561: Got
info_available but entry isn't an iradio station

sometime before the next song it hung. I'm not sure if it was as the song
was ending or not.

Other gstreamer 0.10 programs seems to work fine, like quod libet and totem."