Is concept of similarity objective? Imagine following example:
We have two pairs of points (i.e. 4 objects in some space) and two similarity measures.
According to first similarity measure, objects from first pair are more similar then objects from second pair. On the contrary, according to second similarity measure, objects from the second pair are more similar than objects from the first pair.
Can this happen (i.e. do similarity measures preserve ordering)?
If yes, then does clustering make sense (since we can manipulate with similarity concept by using suitable measure)?
 A: The distance function is an essential input parameter to any distance- or density based clustering algorithm.
Choosing an appropriate distance function is a key step to preparing for data mining. It can be seen as a kind of preprocessing to analyze the various distance functions. And in fact: common data normalization methods - everything that is linear - combined with a Minkowski norm such as Euclidean distance is nothing else than choosing weights for a weighted Euclidean distance right away. So choosing distance functions is even more important than data normalization!
There are in fact very few situations where we know what is the appropriate distance function. Pretty much limited to physics at a medium scale, where "as the crow flies" holds. But assuming you have a data set with two attributes: shoe size and body mass in g. There is no way plain euclidean distance is appropriate, you will at least need to weight it appropriately and assume normal distributions.
A: When you define a similarity, you define it necessarily relatively to one or more parameters.
To elaborate more on Anony-Mousse, well behaving similarity can be roughly defined as the 1-distance (distance of 0 means a similarity of one).
In very simple cases, you can easily distinguish the parameters you want to compare. 
But it's not always easy, especially when their are numerous parameters and/or unknown underlying parameters. For instance imagine you can compare the similarity of 2 movies based on the actors that played in them, and you can define a similarity based on the city where the story is mainly based, etc.
You can easily imagine that those similarities don't need and won't generally be identical.
Now, let's say you want to define a general measure similarity of 2 movies. How can you do it ? There isn't a unique answer. And that's the kind of questions movie recommenders have to struggle with. Some even make contests to find the best answer (http://www.netflixprize.com/).
To understand better, you actually want to find a way to compare movies, so that when you know somebody liked one movie, he will most certainly like all similar movies, based on the note he gave of the movies he previously watched.
Actually all this comes to identify the set of parameters that truly influence the appreciation of a movie. In this case, the winners of the prize used an SVD approach to identify and isolate underlying correlated dimensions (that are not necessarily conceptually understandable and are more complexe to figure than "actors" or "places").
