I've never had to reboot in order to run a new app on linux. If I ever
did, I'd be horrified that linux was turning into microsoft windows. In
the case you mentioned, installing amarok, which is a kde app and you
were looking for it to be in the gnome menu, who knows?

But, I'll bet dollars to doughnuts that if you'd simply logged out and
logged in again, you'd have seen the app in the menu.