I searched for this problem, here and elsewhere, and I seem to be the only one with it. Just upgraded to 9.10 Ubuntu, but I have the KDE desktop installed on top of that. So Amarok is Version 2.2.0, Using KDE 4.3.2.

My problem is that I can so no way to generate a random playlist anymore! I'd gotten used to each of the previous versions back a few years, but searching hasn't shown me the way yet.

Of course I can easily choose an album and have the tracks played randomly, but that is NOT what I want. I want random tracks or random albums from my entire collection. And I want Amarok to generate that playlist.

I don't mind the missing tabs on the side, but how do I get to what used to be in there? I can't find playlists at all -- the playlist menu has no way to CREATE a playlist, only clear one. What am I missing?

You should have a look at dynamic playlists. There is a bug currently that crashes Amarok on start when those are activated, make sure to disable it when leaving. The bug is fixed in upcoming 2.2.1, just around the corner

Hint: Breadcrumb navigation, top left (in default settings)