How do you have them organized on your PC? What version of the software (Rio) are you running?

Any song HAS to be in a playlist in order for you to play it (I don't think you can even search for a song that isn't in a playlist - but I may be wrong on this).

One thing you could do is make a "Whatever You Want To Call It" playlist and put all of your songs in there. Then, you can just randomly suffle from that....

But, if you did a good job of filling out your ID3 tags, AND you are running 2.00beta11, you can go to the "Soup" View and it will have pseudo-playlists (folders really) for each artists or genres or album etc. You can then copy the contents of each of these and make artists folders...