I can find things on my messy desk because I made the mess. If someone else arranged my desk for me, suddenly I have to understand their mental model before I can locate anything.
Which is why I can never, ever find what I'm looking for in Windows' Start menu. Even if the categories seem obvious, they never map 100% to my way of thinking.
(If those categories in the Ubuntu example are user-defined, then they're OK by me.)
…and let's please not even get into how confusing and redundant the Dock looks in the otherwise nice Lion example.