It happens consistently, each time I try to launch the programs. When 
running gst-feedback I get:


[horea@localhost horea]$ gst-feedback
GStreamer feedback script.
Please attach the output of this script to your bug reports.
Bug reports should go into Gnome's bugzilla (http://bugzilla.gnome.org)

+   SYSTEM INFORMATION
+++ uname -a
Linux localhost.localdomain 2.4.18-7.80 #1 Tue Jul 23 18:20:11 EDT 2002 
i686 unknown unknown GNU/Linux
+++  distribution: Red Hat
Red Hat Linux release 7.3.93 (Limbo)
+++ cat /etc/issue
Red Hat Linux release 7.3.93 (Limbo)
Kernel \r on an \m


+   USER INFORMATION
+++ id
uid=501(horea) gid=501(horea) groups=501(horea)

+   PKG-CONFIG INFORMATION
+++ pkg-config --version
0.12.0
+++ pkg-config gstreamer --modversion
0.4.0
+++ pkg-config gstreamer --cflags
-D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -I/usr/include/gstreamer-0.4.0 -
I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -I/usr/incl
ude/libxml2
+++ pkg-config gstreamer --libs
 -L/usr/lib/gst -lgstreamer -lgobject-2.0 -lgmodule-2.0 -ldl -lgthread-
2.0 -lpthread -lxml2 -lz -lm -lglib-2.0
+++ pkg-config gstreamer-libs --modversion
0.4.0
+++ pkg-config gstreamer-libs --cflags
 -I/usr/include/gst-plugins-0.4.0 -I/usr/include/gstreamer-0.4.0 -
I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -I/usr/include/libxm
l2
+++ pkg-config gstreamer-libs --libs
 -L/usr/lib/gst -lgstreamer -lgobject-2.0 -lgmodule-2.0 -ldl -lgthread-
2.0 -lpthread -lxml2 -lz -lm -lglib-2.0

+   GSTREAMER INFORMATION
+++ which gst-register
/usr/bin/gst-register
+++ gst-inspect
INFO (20470: 0) Initializing GStreamer Core Library version 0.4.0
INFO (20470: 0) CPU features: (0c040882) MMX SSE
registry: loaded user_registry in 0.000403 seconds
          (/home/horea/.gstreamer/registry.xml)
+++ gst-inspect fakesrc
INFO (20471: 0) Initializing GStreamer Core Library version 0.4.0
INFO (20471: 0) CPU features: (0c040882) MMX SSE
registry: loaded user_registry in 0.000377 seconds
          (/home/horea/.gstreamer/registry.xml)
no such element or plugin 'fakesrc'
+++ gst-inspect fakesink
INFO (20472: 0) Initializing GStreamer Core Library version 0.4.0
INFO (20472: 0) CPU features: (0c040882) MMX SSE
registry: loaded user_registry in 0.000373 seconds
          (/home/horea/.gstreamer/registry.xml)
no such element or plugin 'fakesink'
+++ gst-launch fakesrc num_buffers=5 ! fakesink
INFO (20473: 0) Initializing GStreamer Core Library version 0.4.0
INFO (20473: 0) CPU features: (0c040882) MMX SSE
registry: loaded user_registry in 0.000364 seconds
          (/home/horea/.gstreamer/registry.xml)

(process:20473): GStreamer-CRITICAL **: file gstscheduler.c: line 743 
(gst_scheduler_factory_find): assertion `name != NULL' failed
(process:20473): [E]xit, [H]alt or [P]roceed:


I guess it is a gstreamer-core bug since it happens with both gst-player 
and rhythmbox.