Songs are not playing, or will sometimes play.

Okay, so I am using Ubuntu, formerly 7.10, then upgraded to 8.0.4.
After the upgrade songs sometimes play. They all appear in the search; they can be clicked on; the title of the clicked on song appears above the slider bar; but the time signature stays at 0:00 and no sound or playing.

Now I've tried different things, installed everything I could find in the Add/Remove thingy that said GStreamer, and I did a Synaptic search for Codecs, thinking installing everything that came up might solve it, and IT DID !!
But... sadley this was short lived. It played the songs after that and then after the program was turned off and restarted: Same issue. I get no error messages, nothing. Just doesn't play.

So then I downloaded Amarok because I was getting fed up, but tried Rhythmbox again after the install, and IT WORKED AGAIN !!!

But again stop working. :-(

This is a case of computer moodiness I haven't seem since the Windows days. I live my Rhythmbox, everything is set up just the way I want it, and I need my music back really bad. Please let there be someone who knows how I can fix this :-(