Instead of mp123 or ogg. Needs a little gst-play binary.
I've also filed an upstream bug for your convenience: http://bugzilla.gnome.org/show_bug.cgi?id=486827
I've sent a patch upstream, pretty crap for integration upstream, but it could be good enough as a vendor patch for Fedora.
Fixed in nautilus-2.20.0-5.fc8